[Leetcode/파이썬] 14. Longest Common Prefix

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: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

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

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters if it is non-empty.

 

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

        for s in strs[1:] :
            while n != 0 :
                if s[:n] == start[:n] : 
                    break
                else :
                    n -= 1
        
        return start[:n]

예에에에에에전에 풀었었는데 까먹어서 다시 기억해내느라 힘들었다. 

Prefix(접두사)의 정의부터 알고 가면 이 문제를 더욱 쉽게 접근할 수 있을 것이라 생각이 든다. pre- 라는 말은 아무래도 앞에 라는 의미가 강하다 보니 쉽게 추측할 수 있는데, 접두사 라는 의미이다. 다시 말해 앞에 붙는다는 말이다. 그렇기 때문에 공통된 가장 긴 접두사는 가장 짧은 단어의 접두사 일 수 밖에 없을 것이고, 그렇게 정렬해서 하나씩 찾아가려고 하였다. (사실 안해도 되는거 같긴 하지만 연산을 덜 할 수 있잖아요?)

길이를 기준으로 정렬을 한 다음 처음에 오는 가장 짧은 단어를 스타트 단어로 선정하고 이 길이를 변수에 저장해 둔다. 

그리고 단어 하나씩 꺼내와서 비교하면서 글자를 하나씩 줄여나가고 만약 두 개가 같은 단어로 좁혀지면 while 문에서 빠져나온다. 

그리고 최종적으로 start 로 지정한 문자와 계산을 마치고 나온 문자 길이를 대입하면 최종적인 공통된 가장 긴 접두사가 남게 된다.