LeetCode - 14번 Longest Common Prefix

LeetCode 14번 Longest Common Prefix

문제

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

Example 1

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

Example 2

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

내 풀이

못 풀어서 모델 솔루션을 봤다! 전에 코드카타에서 봤던 건데 또 못 풀었다!

class Solution:
  def longestCommonPrefix(self, strs: List[str]) -> str:
    if len(strs) == 0:
      return ""
    strs = sorted(strs)
    result = ""
    for letter in strs[0]:
      if strs[-1].startswith(result+letter):
        result += letter
      else:
        break
    return result

일단 빈 리스트가 들어왔을 때 빈 문자열을 리턴한다. 그 외 케이스에서는 리스트를 오름차순으로 정렬하는 sorted 함수로 정렬해준다. 문자열이 있는 리스트는 문자열의 길이순으로 정렬한다. 이렇게 정렬하면 가장 짧은 단어가 가장 앞에, 가장 긴 단어가 가장 마지막에 위치한다.

리스트의 첫 번째 단어이자 가장 짧은 단어의 각 문자를 가장 긴 단어의 시작 문자와 비교한다. 일치하면 결과 문자열에 더해준다. 공통 문자열이 나오지 않을 때까지 반복한다. 공통 문자열이 없으면 반복문을 종료한다.