[LeetCode] Longest Common Prefix

14. Longest Common Prefix

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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

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

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

 

solution

char* longestCommonPrefix(char** strs, int strsSize) {
    if(strsSize == 0) return "";

    char* prefix = strs[0];

    for(int i = 1; i < strsSize; i++) {
        int j = 0;

        while(prefix[j] && strs[i][j] && prefix[j] == strs[i][j]){
            j++;
        }

        prefix[j]= '\0';
    }
    return prefix;
}

prefix를 strs[0]으로 초기화 해서 공통 접두사의 기준으로 삼고, 나머지 문자열들과 비교

prefix[j] = '\0' 으로, 현재 j까지의 공통 부분만 남겨둬서 접두사를 줄여 나가는 방식. 

strs가 ["flower", "flow", "flight"]인 경우

prefix[4] = '\0';  // 이제 prefix는 {'f', 'l', 'o', 'w', '\0', 'r', '\0'}

 

그리고 "flow"와 "flight"를 동일한 방식으로 비교