【leetCode算法-05】最长回文子串问题

最长回文子串是指在一个字符串中找出字典序最大的回文子串。所谓回文子串，就是一个字符串，无论从左往右读还是从右往左读都是一样的。

这个问题的一个关键点在于，如何判断一个字符串是否是回文。一种常见的方法是建立一个字符映射表，然后遍历整个字符串，检查每一个字符出现的次数，如果每个字符出现的次数都是偶数，或者只有一个字符出现奇数次，那么这个字符串就是回文。

另一个关键点是如何有效地查找最长回文子串。我们可以采用动态规划的思想，建立一个二维数组dp，其中dp[i][j]表示字符串s从索引i到j是否是回文。对于每一个dp[i][j]，我们只需要检查s[i]是否等于s[j]，以及dp[i+1][j-1]是否为true即可。这样，我们就可以在O(n^2)的时间复杂度内找到最长回文子串。

以下是具体的Java代码：

public class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; boolean[][] dp = new boolean[s.length()][s.length()]; for (int j = 0; j < s.length(); j++) { dp[j][j] = true; } int maxLen = 1; int start = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) == s.charAt(i + 1)) { dp[i][i + 1] = true; start = i; maxLen = 2; } } for (int k = 3; k <= s.length(); k++) { for (int i = 0; i < s.length() - k + 1; i++) { int j = i + k - 1; if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) { dp[i][j] = true; if (k > maxLen) { start = i; maxLen = k; } } } } return s.substring(start, start + maxLen); } }

在这个例子中，如果我们有以下字符串：

String s = "babad";

那么最长的回文子串是"bab"。这个函数可以正确地返回这个结果。