14. Longest Common Prefix

發表於 更新於 分類於 ， 閱讀次數： Disqus： 文章字數： 215

種類 : string
難度 : easy
題目 : 14.Longest Common Prefix

思維邏輯

  1. 選兩字串，並回傳其中相同的字元
  2. 三字串比較

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def isSame(str_1, str_2):   # 回傳兩字串相同的字元
    temp = ""
    if len(str_1) > len(str_2):
        min_len = len(str_2)
    else:
        min_len = len(str_1)
    for i in range(min_len):
        if str_1[i] == str_2[i]:
            temp += str_1[i]
    return temp

def isCommon(strs): # 回傳三字串相同的字元
    temp_str = ""
    temp_str = isSame(strs[0], strs[1])
    temp_str = isSame(temp_str, strs[2])
    return temp_str

print(isCommon(strs1))

難點

  1. 比較兩字串中相同的字元

最佳解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # 定義一個輸入List[str], 輸出為str的 方法
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        # Assume the first string is the common prefix
        prefix = strs[0]
        
        for s in strs[1:]:
            while s[:len(prefix)] != prefix and prefix:
                # Reduce the prefix by one character
                prefix = prefix[:-1]
            if not prefix:
                break
        
        return prefix

sol = Solution()
print(sol.Solution.longestCommonPrefix(["flower", "flow", "flight"]))   #輸出"fl"
print(sol.Solution.longestCommonPrefix(strs1))  # 與上相同