Leetcode 14. Longest Common Prefix with Python

문제

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

여러 문자열이 주어질 때, 모든 문자열에 공통인 prefix를 리턴하시오.

예시

Input: strs = ["flower","flow","flight"]
Output: "fl"

Input: strs = ["dog","racecar","car"]
Output: ""

제한

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• 문자열은 오직 영어 소문자만을 포함한다.

풀이법

먼저 문자열을 길이 기준 내림차순으로 정렬 한 뒤

맨 앞의 문자열을 기준으로 하여 prefix를 찾는다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs.sort(key=len, reverse=True)
        idx = 0
        ch = ''
        while len(strs[0]) > idx:
            c = strs[0][idx]
            for str in strs:
                if len(str) <= idx or str[idx] != c: return ch
            ch = ch + c
            idx += 1
        return ch