做完前幾天的羅馬數字題，今天換個比較輕鬆的小點心題目：
Longest Common Prefix —— 找出一組字串中最長的共同開頭。

題目核心

我們有一堆字串，要找到它們的「最長共同前綴」。

如果全部字串開頭一樣，就把這一段找出來。

如果根本沒有共同前綴，那就回傳空字串 ""。

範例：

["flower","flow","flight"] → "fl"

["dog","racecar","car"] → ""

解題思路

有幾種常見方法：

水平掃描：
拿第一個字串當基準，然後跟後面的字串一個一個比較，慢慢縮短 prefix。

垂直掃描：
從第 0 個字元開始，檢查所有字串這個位置是否相同。相同就繼續，不同就停。

排序法：
先把陣列排序，然後只要比較第一個字串和最後一個字串，因為它們差異最大。

📝 Java 程式碼（水平掃描法）
class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";

    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
        // 不斷縮短 prefix 直到符合當前字串開頭
        while (strs[i].indexOf(prefix) != 0) {
            prefix = prefix.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }
    }
    return prefix;
}

}

心得

這題不像前幾天的 Roman 系列那麼燒腦，算是送分題。
我覺得它的重點不在演算法本身，而是在不同思路的比較：

水平掃描直覺但有點慢。

垂直掃描更精簡。

排序法蠻聰明，因為只要比第一個跟最後一個字串就好。