今天是紀錄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 "".

寫一個函數尋找出字串陣列中的最長公共前綴字串，如果沒有的話回傳空字串" "

解題思路

我們把第一個字串當作基準，定義i=0~第一個字串長度-1，然後c去遍歷第一個字串的每一個字元，s=其它字串，接著一一比對確定i沒有超過其它字串的長度範圍外，如果第一個字串的c字元等於其它字串的第i個字元，那麼就代表該字元是最長公共前綴字串之一，如果都不符合上述條件的話，代表已經找完所有符合的字元，就回傳找到的最長公共前綴字串

程式碼

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: #如果為空
            return "" #直接回傳空字串

        for i in range(len(strs[0])): #以第一個字串作為基準
            c = strs[0][i] #遍歷第一個字串
            for s in strs[1:]: 
                if i >= len(s) or c != s[i]: #如果超出範圍或找到不符合的字元
                    return strs[0][:i] #回傳前面符合的字元，也就是最長公共前綴字串
        return strs[0]

執行過程

i = 0，c = 'f'

• s = 'flow'

• if i >= len(s) or c != s[i] (i = 0沒超過s的長度4，c = s[0] = 'f')

• s = 'flight'

• if i >= len(s) or c != s[i] (i = 0沒超過s的長度6，c = s[0] = 'f')

i = 1，c = 'l'

• s = 'flow'

• if i >= len(s) or c != s[i] (i = 1沒超過s的長度4，c = s[1] = 'l')

• s = 'flight'

• if i >= len(s) or c != s[i] (i = 1沒超過s的長度6，c = s[1] = 'l')

i = 2，c = 'o'

• s = 'flow'

• if i >= len(s) or c != s[i] (i = 2沒超過s的長度4，c = s[2] = 'o')

• s = 'flight'

• if i >= len(s) or c != s[i] (i = 2沒超過s的長度6，c = 'o' != s[2] = i) → return strs[0][:2]

最後回傳的strs[0][:2]就是回傳'fl'，這樣就找到最長公共前綴字串了