[leetcode] 14. Longest Common Prefix

14. Longest Common Prefix

Easy

35482083Add to ListShare

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:

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

 

제약 사항이 중요하다는 걸 다시 깨달았다.

 

list 길이 자체가 0이 될 수 있어서 방어코드가 필요했다. 첫 두번은 왜 에러가 나는지 몰라 구글링을 통해 이유를 알았다.

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:

        
        list_len = len(strs)
        if list_len == 0: //이 부분이 없어서 두 번 실패
            return ""
        
        min_str = min(strs, key=len)
        print(min_str[0:0])
        pos = 0

        for i in range(len(min_str)):
            pos+=1
            prefx = min_str[0:pos]
            diff = False
            for string in strs:
                if prefx == string[0:pos]: //이 부분을 그냥 string.find를 사용해서 중간에 있는 글자도 검색되어 한번 더 실패.
                    continue
                else:
                    diff = True
                    pos -=1
                    break

            if diff:
                break
                
        return min_str[0:pos]

Details 

Runtime: 36 ms, faster than 54.74% of Python3 online submissions for Longest Common Prefix.

Memory Usage: 14.3 MB, less than 80.25% of Python3 online submissions for Longest Common Prefix.

Next challenges:

Wildcard MatchingForm Largest Integer With Digits That Add up to TargetCheck If Two String Arrays are Equivalent

Show off your acceptance:

 

 

Time SubmittedStatusRuntimeMemoryLanguage

01/16/2021 23:14	Accepted	36 ms	14.3 MB	python3
01/16/2021 23:11	Wrong Answer	N/A	N/A	python3
01/16/2021 23:08	Runtime Error	N/A	N/A	python3
01/16/2021 23:05	Runtime Error	N/A	N/A	python3

 

 

/// vertical 방법

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''

        min_str = min(strs, key=len)
        
        if not min_str:
            return ''
        elif len(strs) == 1:
            return strs[0]
        
        for i in range(len(min_str)):
            prefx = min_str[0:i+1]
            for string in strs:
                if prefx == string[0:i+1]:
                    continue
                else:
                    return prefx[0:len(prefx)-1]
        
        return prefx