[LeetCode] 14. Longest Common Prefix (C++)

문제

문자열 배열이 주어질 때 가장 긴 공통의 prefix 문자열을 찾아라. 없으면 “”를 리턴

생각할 것

1. 배열의 크기가 하나만 있을 때를 생각하기
   a. 문제의 조건 : 1 <= strs.length <= 200
2. string이 ""으로 주어지는 경우를 생각하기
   b. 문제의 조건 : 0 <= strs[i].length <= 200

코드

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res = "";
        bool flag = true;
        int idx = 0;

        while(1){ 
            if(strs.size() == 1) return strs[0];
            for(int i=1; i<strs.size(); i++){
                if(!(idx < strs[i-1].size() && strs[i-1][idx] == strs[i][idx])){
                    flag = false;
                    break;
                }
            } 

            if(flag) {
                res += strs[0][idx];
                idx++;
            }
            else break;
        }

        return res; 
    }
};

처음에는 flag를 이용해 배열의 모든 문자열을 하나씩 비교했었다.

 

코드를 좀더 깔끔하게 바꿀 수 있는 방법이 있을까??

배열을 사전순으로 정렬하고, 첫 문자열과 마지막 문자열의 공통된 부분만 탐색하면 된다!

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
                sort(strs.begin(), strs.end()); // 배열을 사전순으로 정렬 
        string res = "";

                // 정렬된 목록의 첫번째 문자열과 마지막 문자열을 저장 후 두개의 값만 비교
                string first = strs[0];
                string last = strs[strs.size()-1];
        for (int i = 0; i < strs[0].size() ; i++){ 
            if (first[i] == last[i]){ // 같은 문자면 결과 문자열에 더하기  
                res += first[i];
            }
            else break;
        }
        return res;
    }
};