[LeetCode/C++] 14. Longest Common Prefix

---

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return "";
        
        sort(strs.begin(), strs.end());
        string smallest = strs[0];
        string biggest = strs[strs.size()-1];
        string answer = "";
        
        for(int i = 0; i < biggest.size(); i++) {
            if(smallest[i] == biggest[i]) answer += smallest[i];
            else break;
        }
        return answer;
    }
};

---

맨 처음에는 모든 벡터를 돌아가면서 첫 문자부터 가장 길이가 짧은 문자열까지 반복하며 비교하는 것을 생각했습니다.처음에 짠 코드는 맨 아래에 작성했습니다!

 

그 이후 Discussion을 보며 굳이 모두 비교하지 않아도 된다는 것을 알게 되었습니다! 왜냐하면 sort를 하게 되었을 때 문자열이 다르다면 아스키코드순으로 정렬되므로 (ex: apple banana banaoa c..... 식으로) 정렬된다면 맨 처음 문자와 마지막 문자를 비교했을 때 앞에서부터 같은 문자를 확인할 수 있고 문자가 모두 같다면 가장 작은 배열의 길이를 리턴할 수 있겠구나라는 것을 알게 되었습니다.

 

처음 코드에 비해서 최대 5초나 빨라졌지만 여전히 100% 까지는 들어가지 못했습니다. 100% 속도로 푸는 방법을 알고 계시다면 댓글로 설명 부탁드립니다!

---

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.empty()) return "";
        string temp = "";
        int max_length = strs[0].length();
        
        for(int i = 0; i < max_length; i++) {
            for(int j = 0; j < strs.size(); j++) {
                if(max_length < strs[j].length()) max_length = strs[j].length();
                if(i >= strs[j].length()) return temp;
                if(strs[0][i] != strs[j][i]) return temp;
            }
            temp += strs[0][i];
        }
        
        return temp;
    }
};

문제: https://leetcode.com/problems/longest-common-prefix/submissions/

Longest Common Prefix - LeetCode