Leetcode - 14. 最長公共字首

Github位址

文章目錄

• • 思路
  • • 思路1: 橫向掃描法
    • 思路2: 利用Python中zip函數和set
    • 思路3: 利用ASCII碼
  • 編寫

思路

分析了一下題目

思路1: 橫向掃描法

• ①把第一個字元串暫時看做最長公共字首
• ②在第二個字元串看是否能找到目前最長公共字首
• ③如果不能找到,将最長公共字首去掉最後一個,再進行②,
• ④直至比對成功
• ⑤再循環後面的每個元素,總能找到最長公共字首,如果中間最長公共字首為空,直接GG

思路2: 利用Python中zip函數和set

• ①評論區學到的,利用zip函數
• ② 将數組中所有的字元串進行元組化
• ③元組化後,再對每個元組進行set, 就可以看成一個字元串的一個字元
• ④如果set後,長度為 1, 那麼就說明這個數組中每個字元串目前位置的字元都相等

思路3: 利用ASCII碼

—待補充

編寫

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        strsLen = len(strs)
        if(strsLen <= 0): return ''
        ans = strs[0]
        for i in range(1, strsLen):
            while(strs[i].find(ans) != 0):
                ans = ans[:-1]
                if(ans == ''):
                    return ''
        return ans
     # 隻需要找到最長字元串,最短字元串兩者進行比較
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1
    # 評論區學到的,利用zip函數
    # 将數組中所有的字元串進行元組化
    # 元組化後,再對每個元組進行set, 就可以看成一個字元串的一個字元
    # 如果set後,長度為 1, 那麼就說明這個數組中每個字元串目前位置的字元都相等
    def longestCommonPrefix(self, strs):
        prefix = []
        for t in zip(*strs):
            s = set(t)
            if(len(s) == 1):
                prefix.append(s.pop())
            else:
                break
        return "".join(prefix)