14 Longest Common Prefix

1. Description

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

 

constraints :

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

2. Algorithms

To get longest common prefix, we initialize pre, i which stores first string of strs and index of strs. In while loop, if there isn't common prefix, pre becomes shorter when string becomes common prefix of netxt string. 

 

Easy 단계 문제 치고 나에겐 생각보다 어려운 문제였다. while loop에서 if 문을 통해 첫번째 Case를 자동으로 넘기고 두번째 Case와 비교하게 조건문을 설정하는 것은 꽤나 새로운 방식이었다. 이후 교집합이 만족될 때까지 else 문에서 pre(첫번째 원소)를 줄여나가는 알고리즘이다. 

3. Codes

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str : 
        pre = strs[0]
        i = 0 
        
        while i < len(strs) : 
            if strs[i].startswith(pre) : 
                i += 1
            else : 
                pre = pre[:-1]
        return pre

4. Conclusion