[Leetcode] 14. Longest Common Prefix_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '14. Longest Common Prefix'에 대해서 살펴보고자 합니다. 

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Longest Common Prefix' 알고리즘 문제

 

STEP 2. 'Longest Common Prefix' 코드(code)

 

STEP 3. 'Longest Common Prefix' 해설

 

STEP 4. 'Longest Common Prefix' solution

 

반응형

 

STEP 1. '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 "".

 

주어진 문자열에서 가장 긴 접두사(prefix)를 찾습니다. 만약에 공통된 접두사가 없는 경우에는 "" 문자열을 반환합니다.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

---

STEP 2. 'Longest Common Prefix' 코드(code)

 

■ Runtime: 36 ms, faster than 87.85% of Python3 online submissions for Longest Common Prefix.
■ Memory Usage: 13.9 MB, less than 53.26% of Python3 online submissions for Longest Common Prefix.

 

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strs = sorted(strs)
        first = strs[0]
        first_len = len(first)
       
        last = strs[-1]
        last_len = len(last)
        
        word = ""
        
        for i in range(first_len):
            if first[i] == last[i]:
                word += first[i]
            else:
                break

        return word

---

STEP 3. 'Longest Common Prefix' 해설

 

 

 

STEP 4. 'Longest Common Prefix' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 40 ms, faster than 76.29% of Python3 online submissions for Longest Common Prefix.
■ Memory Usage: 13.9 MB, less than 53.26% of Python3 online submissions for Longest Common Prefix.

 

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not strs: return ""
        if len(strs) == 1: return strs[0]
        
        strs.sort()
        p = ""
        for x, y in zip(strs[0], strs[-1]):
            if x == y: p+=x
            else: break
        return p

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '14. Longest Common Prefix'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.