806. Number of Lines To Write String

tags: Easy、String

Given two arrays of strings list1 and list2, find the common strings with the least index sum.
A common string is a string that appeared in both list1 and list2.
A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.
Return all the common strings with the least index sum. Return the answer in any order.

解法:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* numberOfLines(int* widths, int widthsSize, char * s, int* returnSize){
    int* result = (int*)malloc(2* sizeof(int));
    int totalpixels = 0;
    int lines = 1;

    while (*s != '\0') {
        int charwidth = widths[*s - 'a'];
        if (totalpixels + charwidth > 100) {
            lines++;
            totalpixels = charwidth;
        }
        else {
            totalpixels += charwidth;
        }
        s++;
    }
    result[0] = lines;
    result[1] = totalpixels;
    *returnSize = 2;
    return result;
}

599. Minimum Index Sum of Two Lists

tags: Easy、Linked List

Given two arrays of strings list1 and list2, find the common strings with the least index sum.
A common string is a string that appeared in both list1 and list2.
A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.
Return all the common strings with the least index sum. Return the answer in any order.

解法: 雙重for loop

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include <string.h>

char** findRestaurant(char** list1, int list1Size, char** list2, int list2Size, int* returnSize) {
    char** result = (char**)malloc((list1Size > list2Size ? list1Size : list2Size) * sizeof(char*));
    int count = 0;
    int min = INT_MAX;

    if (list1Size > list2Size) {
        for (int i = 0; i < list1Size; i++) {
            for (int j = 0; j < list2Size; j++) {
                if (strcmp(list1[i], list2[j]) == 0) {
                    int sum = i + j;
                    if (sum < min) 
                    {
                        min = sum;
                        count = 0;
                        result[count++] = strdup(list2[j]);
                    } 
                    else if (sum == min) 
                    {
                        result[count++] = strdup(list2[j]);
                    }
                }
            }
        }

    }
    else {
        for (int i = 0; i < list2Size; i++) {
            for (int j = 0; j < list1Size; j++) {
                if (strcmp(list2[i], list1[j]) == 0) {
                    int sum = i + j;
                    if (sum < min) 
                    {
                        min = sum;
                        count = 0;
                        result[count++] = strdup(list1[j]);
                    }
                    else if (sum == min)
                    {
                        result[count++] = strdup(list1[j]);
                    }
                }
            }
        }

    }
    *returnSize = count;
    return result;
}