---

題目鏈接：

14. 最長公共前綴

---

題目描述：

---

解法

解法一：兩兩比較

先算前兩個字符串的最長公共前綴，然后拿這個最長公共前綴和后面一個來比較，得到最長公共前綴。直到比到最后一個字符串。

解法二：統一比較

先比較第一列，然后比較第2列，直到有字符串越界，或者有字符不一樣，停止。

---

C++ 算法代碼：

解法一（兩兩比較）：

class Solution 
{
public:string longestCommonPrefix(vector<string>& strs) {// 解法一：兩兩比較法// 基本思路：先用第一個字符串作為基準，然后依次與后面的每個字符串比較// 每次比較后更新公共前綴，最終得到整個數組的最長公共前綴// 初始化返回結果為第一個字符串// 如果數組為空，此處可能會出錯，但題目通常保證輸入非空string ret = strs[0];// 從第二個字符串開始，依次與當前的公共前綴比較for(int i = 1; i < strs.size(); i++)// 調用輔助函數findCommon計算當前公共前綴與下一個字符串的公共前綴// 并更新公共前綴結果ret = findCommon(ret, strs[i]);// 返回最終的最長公共前綴return ret;}// 輔助函數：計算兩個字符串的最長公共前綴string findCommon(string& s1, string& s2){// 用索引i遍歷兩個字符串int i = 0;// 條件一：確保不越界，只比較到較短字符串的長度// 條件二：當前位置字符必須相同才繼續while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++; // 字符相同，繼續比較下一個字符// 截取s1的前i個字符作為公共前綴返回// 此時i表示公共前綴的長度，可能為0（無公共前綴）// substr(pos,len)返回一個新的字符串，包含原字符串從pos位置開始的len個字符return s1.substr(0, i);}
};

解法二（統一比較）：

class Solution 
{
public:string longestCommonPrefix(vector<string>& strs) {// 解法二：統一比較（逐列比較）// 基本思路：逐個字符位置比較所有字符串，只要發現不一致就立即返回結果// 從第一個字符串的第一個字符開始，逐位置向后比較// strs[0]：訪問字符串數組的第一個元素（即第一個字符串）// strs[0].size()：獲取第一個字符串的長度// i < strs[0].size()：判斷索引i是否小于第一個字符串的長度for(int i = 0; i < strs[0].size(); i++){// 獲取第一個字符串在當前位置的字符作為比較基準char tmp = strs[0][i];// 遍歷剩余的所有字符串，檢查它們在相同位置的字符是否與基準相同// strs：輸入的字符串數組（vector<string>類型）// strs.size()：獲取字符串數組中的字符串數量// j < strs.size()：判斷索引j是否小于數組的大小for(int j = 1; j < strs.size(); j++)// 兩種情況需要立即返回當前已找到的公共前綴：// 1. 當前字符串長度不夠（i已經超出范圍）// 2. 當前字符串在位置i的字符與基準不同// i == strs[j].size()：檢查當前檢查的字符位置i是否等于當前字符串strs[j]的長度。就是"當前字符串是否已經到達末尾？"// tmp != strs[j][i]：檢查基準字符tmp（即第一個字符串在位置i的字符）是否與當前字符串strs[j]在同一位置的字符不同。if(i == strs[j].size() || tmp != strs[j][i])// 返回第一個字符串的前i個字符作為最長公共前綴return strs[0].substr(0, i);}// 如果循環正常結束（沒有提前返回），說明第一個字符串是所有字符串的前綴// 返回第一個字符串作為最長公共前綴return strs[0];}
};

---

解釋

例如：["flower", "flow", "flight"]

執行過程：

1. i=0: 比較所有字符串的第0個字符
   • strs[0][0] = 'f'
   • strs[1][0] = 'f'
   • strs[2][0] = 'f'
   • 全部匹配，繼續
2. i=1: 比較所有字符串的第1個字符
   • strs[0][1] = 'l'
   • strs[1][1] = 'l'
   • strs[2][1] = 'l'
   • 全部匹配，繼續
3. i=2: 比較所有字符串的第2個字符
   • strs[0][2] = 'o'
   • strs[1][2] = 'o'
   • strs[2][2] = 'i' ≠ 'o'
   • 發現不匹配，返回strs[0].substr(0, 2) = “fl”