[LeetCode] 14. Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150 

Longest Common Prefix - LeetCode

문제 유형 : 문자열 처리

문제 난이도 : Easy

 

문제

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 "".

 

문자열들의 배열에서 가장 긴 공통 접두사를 찾아서 반환시키는 함수를 만드시오. 공통 접두사가 없으면 빈 문자열 ""을 반환하시오.

 

풀이

처음에 생각한 풀이 : 모든 문자열을 순회하면서 긴 공통 접두사를 업데이트 하는 방식으로 했다.

이는 최악의 경우 O(n * m)의 속도를 보여준다. (m은 문자열이 모두 같은 길이라는 전체 하에)

 

다른 사람의 풀이 : 정렬 후에 맨 앞과 맨 뒤의 문자열만 비교해서 가장 긴 공통 접두사를 만든다.

C++의 sort는 평균적으로 O(n log n)의 속도를 보여주기 때문에 더 빠르다고 할 수 있다.

 

코드(C++)

처음에 생각한 풀이

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        string prefix = strs[0];
        const int n = strs.size();
        for(int i = 1; i < n; i++){
            string temporary_prefix = "";

            // compare prefix..
            const int len = min(prefix.size(), strs[i].size());
            for(int j = 0; j < len; j++){
                if(prefix[j] == strs[i][j]){
                    temporary_prefix.push_back(prefix[j]);
                }
                else{
                    break;
                }
            }
            prefix = temporary_prefix;
        }
        return prefix;
    }
};

 

정렬을 이용한 풀이

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        string prefix = "";

        sort(strs.begin(), strs.end());

        const string start = strs[0];
        const string end = strs[strs.size()-1];

        for(int i = 0; i < start.size(); i++){
            if(start[i] == end[i]){
                prefix.push_back(start[i]);
            }
            else{
                break;
            }
        }
        
        return prefix;
    }
};