目錄

1. 最長公共前綴

1.1 題目解析

1.2 解法

1.3 代碼實現

2. 最長回文子串

2.1 題目解析

2.2 解法

2.3 代碼實現

---

1. 最長公共前綴

14. 最長公共前綴 - 力扣（LeetCode）

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴，返回空字符串?""。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"

示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共前綴。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]?如果非空，則僅由小寫英文字母組成

1.1 題目解析

題目本質：
在若干字符串中尋找“所有字符串共同擁有的起始前綴”。等價于：找出最小公共“列”的連續一致部分。

常規解法：
1）把第一個串當基準，從左到右逐列比較；
2）每一列都檢查“是否所有字符串在該列字符一致”；
3）一旦某列有人越界或字符不同，前綴到此為止。

問題分析：
最直觀做法已是高效思路：每個字符最多被比較一次，因此總比較次數與所有字符串總長度同階。時間復雜度可以做到 O(S)（S 為全部字符數），空間 O(1)。

思路轉折：
如果直接兩兩比較并把“相同字符累加到全局結果”容易錯，正確做法是統一按列比較（縱向掃描），或者維護前綴并逐步截短（水平掃描）。兩者復雜度相同，縱向掃描實現更直觀、易于避免細節錯誤。

1.2 解法

算法思想：
設基準串 s0 = strs[0]。對位置 i = 0..s0.length()-1：

• 取 ch = s0[i]；

• 對每個其他字符串 sj，若 i >= sj.length() 或 sj[i] != ch，則答案為 s0.substring(0, i)；

• 若全部匹配，繼續下一個位置。
  若循環結束，返回 s0 本身。

i）邊界：若數組為空，返回空串。

ii）外層循環位置 i 遍歷基準串每一位。

iii）內層循環字符串索引 j 從 1 到 n-1，檢查第 i 位是否存在且相等。

iiii）發現不匹配立即返回前綴；全部通過則最終返回基準串。

易錯點：

• 索引混淆： ?內層訪問字符必須用 strs[j].charAt(i)，而不是 strs[i]...。

• substring 語義：?substring(0, i) 的右端不含 i，當 i == 0 返回空串是正確結果。

• 空字符串參與： 若某個字符串長度為 0，第一次比較即返回空串。

• 判空與長度： ?數組用 .length，字符串用 .length()。

1.3 代碼實現

class Solution {public String longestCommonPrefix(String[] strs) {// 1) 邊界處理if (strs == null || strs.length == 0) return "";// 2) 縱向掃描：以第一個字符串為基準，逐列檢查for (int i = 0; i < strs[0].length(); i++) {char ch = strs[0].charAt(i);// 與其余字符串在第 i 位統一比較for (int j = 1; j < strs.length; j++) {// 越界或字符不等：i 之前均為公共前綴if (i >= strs[j].length() || strs[j].charAt(i) != ch) {return strs[0].substring(0, i);}}}// 3) 基準串完全通過：它本身就是最長公共前綴return strs[0];}
}

復雜度分析：

• 時間：O(S)，S 為所有字符串總長度（每個位置最多檢查一次）。

• 空間：O(1) 額外空間（只用常數級變量）。

2. 最長回文子串

5. 最長回文子串 - 力扣（LeetCode）

給你一個字符串?s，找到?s?中最長的?回文?子串。

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。

示例 2：

輸入：s = "cbbd"
輸出："bb"

提示：

• 1 <= s.length <= 1000
• s?僅由數字和英文字母組成

2.1 題目解析

題目本質：
在字符串中找到“關于某一中心左右對稱”的最長連續子串。回文子串可由一個“中心”向兩側對稱擴展得到：奇數長度中心為 (i,i)，偶數長度中心為 (i,i+1)。

常規解法：
暴力枚舉所有子串再判斷是否回文：兩重循環確定區間、再線性判斷。

問題分析：
暴力法需要枚舉 O(n^2) 個區間，每次校驗 O(n)，最壞 O(n^3)，n=1000 時不夠高效。

思路轉折：
要想高效 → 利用“回文圍繞中心對稱”的性質，只需枚舉中心并向兩側擴展。

• 每個中心向外擴的總步數受限于 n，因此總體最壞 O(n^2)；

• 實現簡單、無額外空間；

• 面試與刷題的主流解法（更快的 O(n) Manacher 可作為進階）。

2.2 解法

解法

算法思想：
對每個位置 i：

• 以 (i,i) 作為奇數回文中心擴展，得到長度 len1 = r1-l1-1；

• 以 (i,i+1) 作為偶數回文中心擴展，得到長度 len2 = r2-l2-1；

• 取更長者更新答案起點 begin = L+1 與長度 len。
  擴展結束條件：越界或兩側字符不等。

i）特判：空串或長度 1 直接返回。

ii）初始化 begin=0,len=0。

iii）遍歷中心 i = 0..n-1：

• 令 l=i,r=i，while 兩側相等則擴展；根據 right-left-1 更新答案；

• 令 l=i,r=i+1，同理擴展并比較更新。

iiii）返回 s.substring(begin, begin+len)（右端開區間）。

易錯點：

• 區間邊界：擴展結束時下標已越過合法區間，真正回文是 (left+1, right-1)，長度為 right-left-1；最終 substring 用 [begin, begin+len)。

• 奇/偶中心都要嘗試：只試一種會漏解。

• 變量遮蔽：沒必要定義類字段 left/right，用方法內局部變量即可，避免混淆。

2.3 代碼實現

class Solution {public String longestPalindrome(String s) {int n = s.length();if (n < 2) return s; // 長度為 0/1，自己就是最長回文int begin = 0, len = 1; // 至少有 1 個字符時，單字符是回文for (int i = 0; i < n; i++) {// 奇數中心 (i, i)int l = i, r = i;while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { l--; r++; }if (r - l - 1 > len) {begin = l + 1;len = r - l - 1;}// 偶數中心 (i, i+1)l = i; r = i + 1;while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) { l--; r++; }if (r - l - 1 > len) {begin = l + 1;len = r - l - 1;}}return s.substring(begin, begin + len);}
}

復雜度分析

• 時間：最壞 O(n^2)（每個中心向外擴總步數受限于 n）。

• 空間：O(1) 額外空間。