題目

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

1
2
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2

1
2
3
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 if it is non-empty.

解釋題目

給你一個字串陣列（array of strings），請你找出這些字串的「最長共同前綴」（longest common prefix）。如果沒有任何共同前綴，請回傳空字串 “”

思路

  1. 一個字一個字比對，先比對前兩個單字的最長共同前綴。找出後，再跟第三個單字比對，以此類推。
  2. 在 for 迴圈中運用 while，先假設最長的前綴為第一個單字。
    • 計算最常前綴長度 (prefix_len) 預設是「第一個單字」的長度。
    • 兩兩單字比較時，要取單字的 prefix_len 的長度比較。
    • 若不相等，prefix_len = prefix_len - 1，減少一位比較，直到找出一樣的前綴
    • 如果都沒有一樣的前綴，回傳空字串 ""。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        prefix = strs[0]
        prefix_len = len(prefix)

        for s in strs[1:]:
            while prefix != s[0:prefix_len]:
                prefix_len -= 1
                if prefix_len == 0:
                    return ""
                prefix = prefix[0: prefix_len]
        return prefix