Longest Common Prefix[LeetCode/Python3/Easy]

 

題目

在一個字串陣列中，找出最長的公共前綴字串。

如果沒有公共前綴，回傳空字串 ""。

範例1:

輸入: strs = ["flower","flow","flight"]
輸出: "fl"

範例2:

輸入: strs = ["dog","racecar","car"]
輸出: ""
說明: 輸入字串中沒有公共前綴。

限制條件：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 僅包含小寫英文字母。

我的答案

直覺答案

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

        strs.sort(key=text_length)

        prefix=''
        for j in range(len(strs[0])):
            prefix=prefix+strs[0][j]
            for i in range(1,len(strs)):
                if prefix == strs[i][:j+1]:
                    pass
                else:
                    if prefix:
                        return prefix[:len(prefix)-1]
                    else:
                        return ""
        
        return prefix

可憐的performance😂

改善後的解答

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

        short=min(strs, key=len)
        strs.remove(short)

        prefix=''
        
        for j in range(len(short)):
            prefix=prefix+short[j]
            for i in range(len(strs)):
                if prefix == strs[i][:j+1]:
                    pass
                else:
                    if prefix:
                        return prefix[:-1]
                    else:
                        return ""
        
        return prefix

好吧！至少時間複雜度改善了！不使用sort可以大幅改善時間複雜度！