Leetcode - 14. Longest Common Prefix

문제

문자열이 담긴 백터가 주어질때 모든 문자열에 공통으로 포함된 가장 긴 prefix 문자열을 찾기. (prefix: 문자열 처음부터 시작)

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

해결 O(N M)

idx를 하나씩 늘리며 모든 문자열이 같은지 체크. (이것보다 시간복잡도를 더 빠르게 할수 있나?)

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string longest = "";
        int nr_strs = strs.size();
        int ssize = strs[0].size();
        
        for (int idx = 0; idx < ssize; idx++) {
            int same_cnt = 1;
            for (int elem = 1; elem < nr_strs; elem++) {
                if (strs[elem][idx] == '\0')
                    return longest;
                if (strs[0][idx] != strs[elem][idx])
                    return longest;
                same_cnt++;
            }
            if (same_cnt == nr_strs)
                longest = strs[0].substr(0, idx+1);
        }
        
        return longest;
    }
};

221117 다시 풀어본 풀이

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int idx = 0;
        string longest = "";
        
        while (1) {
            for (int i = 0; i < strs.size(); i++) {
                if (strs[i][idx] == '\0' || strs[i][idx] != strs[0][idx])
                    return longest;
            }
            longest = longest + strs[0][idx];
            idx++;
        }
        return longest;
    }
};