最长回文子串：探索Java编程中的经典问题
一、问题背景
在Java编程中，字符串处理是一个常见的任务。其中，最长回文子串（Longest Palindromic Substring）问题是一个经典的字符串处理问题。该问题要求在一个字符串中找到最长的回文子串，并返回其长度。回文是指正读和反读都相同的字符串，如“abba”、“madam”等。
二、问题分析
最长回文子串问题可以通过多种方法解决，但其中最经典的方法是动态规划（Dynamic Programming，DP）和中心扩展法。下面将分别介绍这两种方法。
1. 动态规划
动态规划是一种解决序列问题的有效方法。在最长回文子串问题中，我们可以通过构建一个二维数组dp来记录子串是否为回文。dp[i][j]表示从字符串的第i个字符到第j个字符的子串是否为回文。
状态转移方程如下：
- 如果s[i] == s[j]，则dp[i][j] = dp[i+1][j-1]
- 否则，dp[i][j] = false
接下来，我们需要遍历整个二维数组，找出dp[i][j]为true的子串，并记录其长度。
2. 中心扩展法
中心扩展法是一种更直观的解决方法。对于字符串中的每个字符，我们可以将其视为回文子串的中心。由于回文子串可能为奇数或偶数长度，因此我们需要考虑两种情况。
- 对于奇数长度的回文子串，以字符为中心，向左右扩展，判断扩展后的子串是否为回文。
- 对于偶数长度的回文子串，以两个字符之间的空隙为中心，向左右扩展，判断扩展后的子串是否为回文。
遍历字符串中的每个字符，记录最长回文子串的长度。
三、Java实现
以下是用Java实现最长回文子串问题的代码示例。
```java
public class LongestPalindromeSubstring {
// 动态规划法
public int longestPalindromeDP(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxLen = 1;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
maxLen = Math.max(maxLen, len);
}
}
}
return maxLen;
}
// 中心扩展法
public int longestPalindromeCE(String s) {
int n = s.length();
int maxLen = 0;
for (int i = 0; i < n; i++) {
// 奇数长度的回文子串
int len1 = expandAroundCenter(s, i, i);
// 偶数长度的回文子串
int len2 = expandAroundCenter(s, i, i + 1);
maxLen = Math.max(maxLen, Math.max(len1, len2));
}
return maxLen;
}
private int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
// 返回回文子串的长度
return right - left - 1;
}
public static void main(String[] args) {
LongestPalindromeSubstring lps = new LongestPalindromeSubstring();
String s = "babad";
System.out.println("最长回文子串长度：" + lps.longestPalindromeDP(s));
System.out.println("最长回文子串长度：" + lps.longestPalindromeCE(s));
}
}
```
四、总结
本文介绍了最长回文子串问题，并分析了两种常用的解决方法：动态规划法和中心扩展法。通过Java代码示例，展示了如何实现这两种方法。在实际应用中，我们可以根据具体需求选择合适的方法来解决最长回文子串问题。
