14. Longest Common Prefix

Easy

Description

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

Example:

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

Intuition#

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

公共前綴的長度不會超過最短字串的長度
可以垂直掃描（逐字元比較所有字串）或水平掃描（逐一縮短前綴）

Approaches#

1: 水平掃描#

概念: 以第一個字串為初始前綴，依次與後續字串比較，逐步縮短前綴
時間複雜度: O(S) - S 為所有字串字元總數
空間複雜度: 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: 垂直掃描#

概念: 逐字元位置比較所有字串，遇到不匹配或字串結束就停止
時間複雜度: O(S) - S 為所有字串字元總數（最壞情況）
空間複雜度: 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]
    }
}

補充：排序後比較首尾

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

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#

Pattern: 多字串比對的經典題，垂直掃描最直觀且能提前終止
關鍵技巧: 排序後比較首尾是巧妙的技巧，因為字典序排序後差異最大的一定是首尾兩個字串