LeetCode : 14. Longest Common Prefix

예전에 백준에서 비슷한 문제였던 전화번호 목록?을 풀었던 기억이 있어서 비교적 쉽게 접근할 수 있었다.

 

[메인 아이디어]

일단, 문자열 배열을 정렬하면 어떤식으로 정렬이 되는 지를 알아야 하는게 우선이다!

문자열 배열 ["flower", "flow", "flo", "fl", "snack", "sna", "s"]를 정렬하면,

["fl", "flo", "flow", "flower", "s", "sna", "snack"] 과 같이 정렬이 된다.

즉, 접두사가 일치하는 문자열 끼리 정렬이 되고 그 후에 알파벳 순서로 정렬된다.

위의 특성을 잘 활용하면 문제를 빠르게 풀 수 있다.

 

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string ans = "";
        if(strs.size()==0){
            return ans;
        }
        sort(strs.begin(), strs.end());
        string s = strs[0];
        string temp = "";
        
        if(strs.size()==1){
            return s;
        }
        
        for(int i=0; i<s.size(); i++){
            temp += s[i];
            for(int j=1; j<strs.size(); j++){
                if(temp!=strs[j].substr(0, i+1)){
                    return ans;
                }
            }
            
            ans = temp;
        }
        
        return ans;
    }
};