#14

Longest Common Prefix ↗

Easy草稿★★★★★⭐ O(S) 時間 · O(1) 空間
String
尚未複習過

解法已隱藏 — 先讀題目敘述、自己想想看，再點上方按鈕揭曉。

14Longest Common PrefixArrays & HashingEasyArrays & Hashing

找出字串陣列中所有字串的最長公共前綴。如果不存在公共前綴，回傳空字串 ""。

Example:

Input: strs = [“flower”,“flow”,“flight”] Output: “fl”

Intuition

TIP

核心思路：逐字元比對所有字串，只要有一個字串不匹配就停止。

Approaches

1. Horizontal Scan — O(S) / O(1)
  • Idea: 以第一個字串為初始前綴，依次與後續字串比較，逐步縮短前綴
  • Time: O(S) - S 為所有字串字元總數
  • Space: O(1) - 只用指標
class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        var prefix = strs[0]
        for (i in 1 until strs.size) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length - 1)
                if (prefix.isEmpty()) return ""
            }
        }
        return prefix
    }
}
⭐ 2. Vertical Scan — O(S) / O(1)
  • Idea: 逐字元位置比較所有字串，遇到不匹配或字串結束就停止
  • Time: O(S) - S 為所有字串字元總數（最壞情況）
  • Space: O(1) - 只用索引
class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        for (i in strs[0].indices) {
            val c = strs[0][i]
            for (j in 1 until strs.size) {
                if (i >= strs[j].length || strs[j][i] != c) {
                    return strs[0].substring(0, i)
                }
            }
        }
        return strs[0]
    }
}
Note: Sort then Compare Ends

排序後，最長公共前綴只需比較第一個和最後一個字串（因為排序保證了字典序的最大差異在首尾）。

class Solution {
    fun longestCommonPrefix(strs: Array<String>): String {
        strs.sort()
        val first = strs.first()
        val last = strs.last()
        var i = 0
        while (i < first.length && i < last.length && first[i] == last[i]) {
            i++
        }
        return first.substring(0, i)
    }
}

🔑 Takeaways