LeetCode - 14. Longest Common Prefix (Python)

Easy, 접두어 찾기

RunTime : 42 ms / Memory : 16.4 MB

문제

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

풀이

• 42ms 풀이, 길이 순으로 정렬해서 가장 짧은 걸 기준으로 삼아 해당 값과 이후 값들을 비교해주었다.

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

        if len(strs) == 0:
            return ""
        else:
            for i in range(len(strs[0])):
                for j in range(1, len(strs)):
                    if strs[0][i] != strs[j][i]:
                        return strs[0][:i]
            return strs[0]

• 32ms 풀이 (참조), 단순 sorted()를 하면 사전순으로 정렬이 되는데, 이를 통해
  [0]과 [-1]을 비교해 보다 빠르게 답을 구할 수 있다.

class Solution:
    def longestCommonPrefix(self, v: List[str]) -> str:
        ans =""
        v = sorted(v)
        first = v[0]
        last = v[-1]
        for i in range (min(len(first),len(last))):
            if(first[i] != last[i]):
                return ans
            ans += first[i]
        return ans