目录
1. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"] 输出："fl"
示例 2：
输入：strs = ["dog","racecar","car"] 输出："" 解释：输入不存在公共前缀。
提示：
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[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. 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
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) 额外空间。