A 2ms C solution


  • 0
    G
    char* longestCommonPrefix(char** strs, int strsSize) {
        char *currentPrefix = "";
        int currentPrefixLength;
        for (int i = 0; i < strsSize; i++) {
            int strLen = strlen(strs[i]);
            char *str = strs[i];
            if (i == 0) {
                currentPrefix = malloc(sizeof(char)*(strLen+1));
                currentPrefixLength = strLen;
                strcpy(currentPrefix,str);
            }
            else {
                for (int k = 0; k < strLen + 1; k++) {
                        if (currentPrefix[k] != str[k]) {
                            str[k] = 0;
                            strcpy(currentPrefix,str);
                            currentPrefixLength = strLen + 1;
                            break;
                        }
                }
            }
        }
        return currentPrefix;
    }
    

    If the provided string array is empty, the for loop is skipped and the default empty string is returned. Otherwise, the first string of the array is considered our current "common prefix". If the later strings in the array fail to match up against it, we trim down our current prefix by copying the string which does not match all the way up to the point where is diverges. This is represented by the line str[k] = 0, which inserts the null terminator at this point. The modified string is copied to our current prefix and this process is repeated.

    We could avoid destroying/messing up the original array by copying each string in the array to another string before performing the check against the current prefix.


  • 0
    V
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.