[LeetCode] 14. Longest Common Prefix (python3)

 

https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

 

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.

 

Solution: O(nlogn)

- sort array

- just compare first string and last string to get LCP

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if len(strs) == 1: return strs[0]
        
        strs.sort()
        
        if strs[0] == "": return ""
        
        prefix = ""

        for i, char in enumerate(strs[0]):
            if char == strs[-1][i]:
                prefix += char
            else:
                break
        
        return prefix

 

Solition2: O(n)

작성중