1. 问题理解与基础解法
1.1 回文子串的定义与特性
回文子串是指正读和反读都相同的字符串片段。例如"aba"、"abba"都是回文子串。理解回文子串的特性是解决这个问题的关键：
- 对称性：所有回文子串都具有对称结构
- 中心扩展性：可以从中心向两边扩展判断
- 子结构特性：长回文子串的子串也是回文
在C++中，字符串以'\0'结尾，但std::string已经封装了长度信息，我们可以直接使用size()方法获取长度。
1.2 暴力解法实现与优化
暴力解法是最直观的解决方案，虽然时间复杂度较高(O(n³))，但对于理解问题本质很有帮助。以下是优化后的暴力解法实现：
cpp复制class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
if (s.size() == 1) return s;
int max_len = 1;
int start = 0;
for (int i = 0; i < s.size(); ++i) {
for (int j = i + 1; j < s.size(); ++j) {
if (j - i + 1 > max_len && isPalindrome(s, i, j)) {
max_len = j - i + 1;
start = i;
}
}
}
return s.substr(start, max_len);
}
private:
bool isPalindrome(const string& s, int left, int right) {
while (left < right) {
if (s[left++] != s[right--]) {
return false;
}
}
return true;
}
};
注意：暴力解法在LeetCode上可能会因为超时而无法通过所有测试用例，但对于小规模字符串仍然是一个可行的选择。
1.3 边界条件处理
在实际编码中，我们需要特别注意以下边界条件：
- 空字符串输入
- 单字符字符串
- 全相同字符的字符串
- 无重复字符的字符串
2. 中心扩展法详解
2.1 算法原理与实现
中心扩展法利用了回文串的对称特性，将时间复杂度降低到了O(n²)。核心思想是：每个回文串都有一个中心，可以从中心向两边扩展判断。
cpp复制class Solution {
public:
string longestPalindrome(string s) {
if (s.size() <= 1) return s;
int start = 0, max_len = 1;
for (int i = 0; i < s.size(); ++i) {
int len1 = expandAroundCenter(s, i, i); // 奇数长度
int len2 = expandAroundCenter(s, i, i+1); // 偶数长度
int current_max = max(len1, len2);
if (current_max > max_len) {
max_len = current_max;
start = i - (max_len - 1) / 2;
}
}
return s.substr(start, max_len);
}
private:
int expandAroundCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
};
2.2 性能分析与优化
中心扩展法的优势在于：
- 时间复杂度O(n²)，空间复杂度O(1)
- 实现简单直观
- 不需要额外存储空间
在实际应用中，我们可以进行以下优化：
- 提前终止：当剩余可能的最大长度小于当前找到的最大长度时，可以提前终止循环
- 跳跃检查：发现长回文后，可以跳过一些不可能形成更长回文的中心点
3. 动态规划解法深入
3.1 动态规划思路解析
动态规划是解决最长回文子串问题的另一种有效方法。我们定义dp[i][j]表示子串s[i...j]是否为回文。
状态转移方程：
- dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i+1][j-1])
初始化条件：
- dp[i][i] = true (单个字符都是回文)
3.2 完整实现代码
cpp复制class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n <= 1) return s;
vector<vector<bool>> dp(n, vector<bool>(n, false));
int start = 0, max_len = 1;
// 初始化长度为1的子串
for (int i = 0; i < n; ++i) {
dp[i][i] = true;
}
// 检查长度为2的子串
for (int i = 0; i < n - 1; ++i) {
if (s[i] == s[i+1]) {
dp[i][i+1] = true;
start = i;
max_len = 2;
}
}
// 检查长度大于2的子串
for (int len = 3; len <= n; ++len) {
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && dp[i+1][j-1]) {
dp[i][j] = true;
if (len > max_len) {
start = i;
max_len = len;
}
}
}
}
return s.substr(start, max_len);
}
};
3.3 复杂度分析与比较
动态规划解法的时间复杂度为O(n²)，空间复杂度也是O(n²)。相比中心扩展法：
- 优点：思路更加系统化，适合解决更复杂的子串问题
- 缺点：需要额外的存储空间
在实际应用中，当字符串长度非常大时，中心扩展法通常是更好的选择。
4. 算法选择与实战建议
4.1 不同场景下的算法选择
- 小规模字符串：暴力解法简单直接
- 一般规模字符串：中心扩展法效率高
- 需要解决相关子串问题时：动态规划更灵活
- 超大规模字符串：可能需要Manacher算法(O(n)复杂度)
4.2 常见错误与调试技巧
在实现这些算法时，开发者常会遇到以下问题：
-
边界条件处理不当：
- 空字符串
- 单字符字符串
- 全相同字符的字符串
-
下标计算错误：
- 回文子串起始位置计算错误
- 扩展时边界判断错误
-
性能问题：
- 不必要的重复计算
- 没有利用已知信息进行优化
调试时可以：
- 打印中间状态变量
- 使用简单测试用例验证
- 逐步增加输入规模测试
4.3 LeetCode提交注意事项
在LeetCode上提交代码时，建议：
- 先测试边界条件
- 检查内存使用情况
- 比较不同解法的运行时间
- 注意函数签名和返回值类型
对于最长回文子串问题，中心扩展法在大多数情况下是最优选择，它在时间和空间复杂度之间取得了良好的平衡。