LeetCode - 14. Longest Common Prefix

문제 개요

난이도 - EASY 사용 언어 - C++

문자열 리스트가 주어질 때 가장 긴 접두사를 찾으면 됩니다.

예를 들어 ["flower","flow","flight"]가 주어졌다면 모든 문자열에 fl이라는 접두사가 붙었으니 해당 문자열을 반환하면 됩니다.

반대로 ["dog","racecar","car"]라는 입력이 주어졌다면 모든 문자열에 공통이 되는 접두사가 없으므로 빈 문자열을 반환하면 됩니다.

문제 - LeetCode 14. Longest Common Prefix

풀이

My Solutions(Github)

Solution

첫 번째로 고려해야 하는 조건은 접두사는 모든 문자열의 길이보다 작거나 같아야합니다. 다른 문자열의 길이보다 접두사가 더 길면 접두사가 될 수 없기때문입니다.

두 번째로 한 문자열의 전체가 다른 문자열의 접두사가 될 수로 있습니다. 예를 들어 flow라는 문자열은 flower의 접두사가 될 수 있겠죠.

string& prefix = strs[0];
 
for (int i = 1; i < length ; i++)
{
    ...
}

첫 번째 문자열을 선택하여 순회를 시작합니다. 다른 문자열을 선택해도 충분히 문제가 없을 듯 합니다. 하지만, 코드의 가독성을 위해 첫 번째나 마지막 문자열을 선택하는 것이 가장 좋은 선택지가 될 것 같네요.

if (prefix.size() > strs[i].size())
{
    prefix = prefix.substr(0, strs[i].size());
}

문자열을 순회하던 중 현재 선택된 접두사가 문자열보다 더 길다면 문자열의 길이로 축소합니다. 그리고 한 문자열이 다른 문자열의 접두사가 될 수 있으므로 더 줄일 필요는 없을 것 같습니다.

for (int j = 0; j < prefix.size(); j++)
{
    if (prefix[j] != strs[i][j])
    {
        prefix = prefix.substr(0, j);
    }
}

이제 접두사와 문자열을 비교합니다. 가장 긴 공통된 접두사를 찾는 문제이므로 접두사와 다른 문자를 발견한다면 접두사의 길이를 공통된 부분까지만 축소합니다.

if (prefix.size() == 0) break;

문자열을 계속 순회하던 중 접두사의 길이가 0이되면 순회를 탈출하는 것이 소소한 최적화에 도움이 될 것 같습니다.

제출 결과

Solution 1 result

문제 자체가 시워서 첫 시도만에 100%의 성능을 보이는 코드를 작성할 수 있었습니다.

코드 전문

class Solution 
{
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        int length = strs.size();
 
        if (length == 0) return "";
        else if (length == 1) return strs[0];
 
        string& prefix = strs[0];
 
        for (int i = 1; i < length ; i++)
        {
            if (prefix.size() > strs[i].size())
            {
                prefix = prefix.substr(0, strs[i].size());
            }
 
            for (int j = 0; j < prefix.size(); j++)
            {
                if (prefix[j] != strs[i][j])
                {
                    prefix = prefix.substr(0, j);
                }
            }
 
            if (prefix.size() == 0) break;
        }
 
        return prefix;
    }
};

LeetCode - 14. Longest Common Prefix LeetCode

목차

문제 개요

풀이

Solution

제출 결과