[LeetCode]Longest Common Prefix

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

Longest Common Prefix - LeetCode

 

문제 분석

주어진 문자열에서 가장 긴 prefix를 찾아내는 문제입니다.

 

처음 시도한 답안

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs.sort(key=len)

        output = ""
        for idx, char_ in enumerate(strs[0]):
            flag = []
            for str_ in strs[1:]:
                if char_ == str_[idx]:
                    flag.append(True)
                else:
                    flag.append(False)
            if all(flag):
                output += char_
            else: 
                break

        return output

접근 방법

1. 가장 짧은 문자가 앞으로 오도록 정렬합니다.
2. 가장 짧은 문자열을 순회합니다.
3. 나머지 문자열을 순회하면서 같은 인덱스 위치에서, 같은 prefix를 가지는지 판단합니다.
4. 맞다면 flag에 True, 틀린 곳이 있다면 False를 넣습니다.
5. flag에 모두 True만 담겨 있다면 output 에 prefix를 하나씩 추가합니다.
6. 아니라면 더이상 prefix는 존재하지 않으므로 빠져 나옵니다.

처음에는 가장 짧은 문자열 길이만큼 반복하면서, 나머지 문자열들도 2중 순회를 통해 같은 prefix를 가지는지 판단하는 방법으로 구현 했습니다. 문제자체는 풀 수 있었으나 다른 분들의 답안을 참고하여 코드를 최적화 해보았습니다.

(ps. `.sort()` 의 시간 복잡도는 O(n log n) 입니다.)

 

두번째로 시도한 답안

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
        	return ''
    
        min_str = min(strs, key=len)

        for idx, val in enumerate(min_str):
            for str_ in strs:
                if str_[idx] != val:
                    return min_str[:idx]

        return min_str

접근 방법

1. 문자열이 없다면 ''를 early return 합니다.
2. 문자열의 길이가 가장 적은 문자열을 min 함수로 찾아냅니다.
3. 가장 짧은 문자열을 순회합니다. (가장 길이가 짧은 문자열보다 common prefix가 존재할수는 없습니다.)
4. 2중 순회로 문자열을 순회합니다.
5. 그 때 값이 같은 인덱스에 위치한 문자가 다르다면 해당 인덱스 전까지 슬라이싱해 return 합니다.
6. 모두 같다면 min_str을 return 합니다.

두번째로 시도한 방법은 첫번째에 비해 최적화 되어 있습니다. 특히 다른 문자열을 모두 순회하지 않고 prefix가 틀리다면 그 시점에 바로 함수를 종료하게 됩니다. flag 같은 것이 존재하지 않아, 코드 또한 이해하기에 쉬워졌습니다.

(ps. `min()` 의 시간 복잡도는 O(n) 입니다.)