14. Longest Common Prefix

https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

 

문자열이 여러개 주어졌을 때, 그 문자열들 중에서 가장 긴 공통 접두사문자열을 찾는 문제다.

풀이법으로는

 

1. 문자열 중 가장 짧은 길이를 찾는다.

2. 모든 문자열을 문자 순서대로 탐색한다.

3. 탐색하며 모든 문자열이 같으면 누적하고, 다르면 바로 리턴한다.

 

1. 모든 문자열을 순서대로 정렬한다.

2. 가장 첫 문자열과 끝 문자열이 가장 많이 차이나므로 둘만 비교해도 충분하다.

 

Input: [""] 일 때 에러 발생으로 첫번째 if문 추가

Input: ["",""] 일 때 에러 발생으로 두번째 if문 추가

 

[C++]

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) {
            return "";
        }
        
        if (strs[0].empty()) {
            return strs[0];
        }
        
        sort(strs.begin(), strs.end());
        
        string ret;
        int size = strs.size();

        for (int i = 0; i <strs[0].size(); ++i)
        {
            if (strs[0][i] != strs[size - 1][i]) {
                return ret;
            }
            
            ret += strs[0][i];
        }
        
        return ret;
    }
};

 

[Python3]

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        ret = str()
        strs.sort()
        
        for i in range(0, len(strs[0])):
            if strs[0][i] != strs[-1][i]:
                print("exit")
                return strs[0][:i]
        return strs[0]