l
14. Longest Common Prefix

這是關於最長共同前綴的演算法問題。

這題的目標是給定一個字串陣列（strs），要找出一個最長且所有字串都共有的前綴字串。其中，有幾個名詞需要解釋：

前綴（Prefix）：一個字串開頭的部分。例如，"flow”的前綴可以是""、"f"、"fl"、"flo"、"flow"。

共同前綴（Common Prefix）：如果一個字串是陣列中所有字串的前綴，它就是共同前綴。

最長共同前綴（Longest Commom Prefix, LCP）：在所有共同前綴中，長度最長的那一個。

如果沒有共同前綴（例如，第一個字母就不同），則返回空字串""。

這題有很多解決方法，而其中最直觀且效率較高的方法是垂直掃描法（Vertical Scanning）。
首先，取第一個字串為基準： 假設第一個字串（strs[0]）就是可能的 LCP，並以它的長度作為最長可能前綴的界線。
接著，逐字元比較：從第一個字元的索引 i=0 開始，依序往後遍歷第一個字串的每個字元。在每個索引 i 處，將第一個字串的第 i 個字元 (strs[0].charAt(i)) 與陣列中所有其他字串（strs[1] 到 strs[n-1]）的第 i 個字元進行比較。
再來是終止條件： 遇到以下兩種情況，說明已經找到 LCP 的終點，此時即可返回結果：
越界： 當遍歷到某個字串的長度已經短於 i 時，表示該字串已經結束，後續字元不可能再是共同前綴。
字元不匹配： 某個字串在索引 i 上的字元與第一個字串的字元不相同。
如果是因為上述兩個條件之一而停止，那麼共同前綴就是第一個字串從開頭到索引 i 之前的部分，就可以返回結果，使用 strs[0].substring(0, i) 來取得這部分字串。
如果整個第一個字串都被掃完： 如果迴圈跑完第一個字串的所有字元都沒有觸發終止條件，表示第一個字串本身就是 LCP。

複雜度分析
時間複雜度： O(S)
S 代表所有字串的字元總數。在最差的情況下（例如 ["aaaaa", "aaaaa", "aaaaa"]），我們需要遍歷所有字串的所有字元，因此時間複雜度取決於總字元數。
更精確地說，如果 N 是字串的數量， M 是最短字串的長度，則時間複雜度為 O(N⋅M)。
空間複雜度： O(1) 或 O(M)
如果不計算返回結果字串所佔用的空間，則空間複雜度為 O(1) (只使用了固定數量的變數)。如果將返回的最長共同前綴的長度 M 也算作空間，則為 O(M)。