題目:
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
編寫一個函數來尋找字串陣列中的最長公共前綴字串。
如果沒有公共前綴，則傳回空字串""。
解題思路
方法一：逐字比較（直觀解法）
假設第一個字串是基準前綴。
從第二個字串開始，不斷縮短基準前綴，直到它能匹配當前字串的開頭。
遍歷完所有字串後，基準前綴就是答案。
時間複雜度：O(m × n)，m = 最短字串長度，n = 字串數量。
方法二：垂直掃描
從第 0 個字元開始，檢查所有字串的同一個位置是否相同。
一旦遇到不相同或有字串結束，返回當前累積的前綴。
方法三：分治法 / 字典樹（進階）
可以用分治法（Divide and Conquer）或 Trie（字典樹）優化。
但面試通常方法一或二就足夠。
iThome鐵人賽
看影片追技術