[LeetCode] Strings > Longest Common Prefix

https://leetcode.com/explore/interview/card/top-interview-questions-easy/127/strings/887/

Explore - LeetCode

---

풀이

 

Prefix 검증의 기준 문자열을 가장 길이가 짧은 문자열로 잡고 진행

기준 문자열[i] 과 다른 모든 문자열의 [i]가 같다면 prefix_idx를 +1해준다. 만약 다른 문자열이 존재한다면 prefix가 아니므로 break하여 빠져나온다.

 

EX)
strs = ["flower","flow","flight"] ==> 길이 순으로 오름차순 정렬
strs = ["flow", "flower", "flight"] ==> 길이가 가장 짧은 "flow"가 기준 문자열

* step 1
기준 문자열 strs[0][0]와 나머지 문자열 strs[1][0], strs[2][0] 이 동일하므로 prefix_idx는 +1 되어
현재 prefix는 strs[0][0:1] ==> "f"

* step 2
기준 문자열 strs[0][1]와 나머지 문자열 strs[1][1], strs[2][1] 이 동일하므로 prefix_idx는 +1 되어
현재 prefix는 strs[0][0:2] ==> "fl"

* step 3
기준 문자열 strs[0][2]와 strs[1][2]은 동일하지만 strs[2][2]은 다르기 때문에 break 최종 prefix_idx는 2
최종 prefix "fl" 리턴

 

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs = sorted(strs, key=lambda x: len(x))
        end = 0
        for i in range(len(strs[0])):
            for j in range(1, len(strs)):
                if strs[j][i] == strs[0][i]:
                    pass
                else:
                    break
            else:
                end += 1
                continue
            break
        return strs[0][0:end]