数据结构与算法面试题：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。（提示：使用动态规划或者中心扩散）
简介：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。（提示：使用动态规划或者中心扩散）
算法思路
算法思路：
回文串是一个正反读都相同的字符串，在本题中需要找到最长的回文子串。首先考虑暴力解法，枚举所有可能的子串，并判断是否为回文串。时间复杂度为O ( n 3 ) O(n^3)O(n3)，无法通过本题。
因此可以使用动态规划和中心扩散两种方法来提高效率，其中较为简单的是中心扩散。我们发现，回文串是以中心对称的，可以想到从每个字符作为中心，向两边扩展找出回文串，然后取长度最长的作为答案。在具体实现时，注意回文串长度可能是奇数或偶数，属于两种情况，需要分别考虑。时间复杂度为O ( n 2 ) O(n^2)O(n2)。
下面是C++代码实现，注释已加入：
#include <iostream> #include <string> using namespace std; // 中心扩散法寻找回文子串 string longestPalindrome(string s) { int n = s.size(); if (n < 2) return s; // 字符串长度小于2则直接返回s int start = 0, len = 0; // 记录最长回文子串的起点和长度 for (int i = 0; i < n; ++i) { // 枚举中心点i // 分别处理回文子串长度为奇数、偶数的情况 for (int k = 0; k < 2; ++k) { int left = i, right = i + k; while (left >= 0 && right < n && s[left] == s[right]) { --left; ++right; } // 当前回文子串长度为(right - 1) - (left + 1) + 1 = right - left - 1 int cur_len = right - left - 1; if (cur_len > len) { // 更新最长回文子串 start = left + 1; len = cur_len; } } } return s.substr(start, len); // 返回最长回文子串 } int main() { string s = "babad"; string ans = longestPalindrome(s); cout << ans << endl; return 0; }
其中，首先判断字符串长度是否小于2，如果是则直接返回原字符串。然后从每个字符位置分别向两边扩展，寻找回文子串。需要注意的是，在枚举中心点时需要分别处理回文子串长度为奇数和偶数的情况（即中间一个字符和中间两个字符），同时在扩展回文子串时需要判断左右指针是否越界，并且注意当前回文子串长度的计算方式。最后返回最长回文子串即可。
- Java
public class Main { public static String longestPalindrome(String s) { int n = s.length(); if (n < 2) return s; int start = 0, len = 0; for (int i = 0; i < n; ++i) { for (int k = 0; k < 2; ++k) { int left = i, right = i + k; while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) { --left; ++right; } int curLen = right - left - 1; if (curLen > len) { start = left + 1; len = curLen; } } } return s.substring(start, start + len); } public static void main(String[] args) { String s = "babad"; String ans = longestPalindrome(s); System.out.println(ans); // "bab" } }
