Longest Common Prefix

Description#

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Approach#

Special cases: Return "" when the array is empty, return the single element when the array has only one element.
Start from the first letter, check if each element's first letter is the same as the first element's first letter, then continue to the second letter.
- Special cases:
  1. Current letter is empty: Since we are checking letters from the beginning, the current string is the shortest, so return the current string.
  2. Current letter is different from the first element's current letter: Indicates that the current letter of the first element should be truncated to '\0', then return the first element.

char * longestCommonPrefix(char ** strs, int strsSize){
    if(strsSize == 0 )
        return "";
    if(strsSize == 1)
        return strs[0]; 
    for(int i=0;;i++) {
        for(int j=0;j<strsSize;j++) {
            if(strs[j][i] == 0)
                return strs[j];
            if(strs[0][i] != strs[j][i]) {
                strs[0][i] = '\0';
                return strs[0];
            }   
        }
    }
}

Note#

Initially, I only thought of checking column by column and returning when encountering different elements. It was during the debugging process that I discovered the need for special handling of certain cases.