Java编程实战：深入解析“最长回文子串”问题
在Java编程的世界里，算法题是程序员们必须面对的挑战之一。其中，“最长回文子串”问题就是一道经典的面试题，它不仅考察了我们对字符串操作的理解，还考验了我们的算法设计能力。本文将结合实际编程经验，深入解析“最长回文子串”问题，并提供几种不同的解决方案。
一、问题背景
回文串是指正读和反读都相同的字符串。例如，“abba”、“madam”和“racecar”都是回文串。而“最长回文子串”问题则是要求我们在一个给定的字符串中找出最长的回文子串。
二、暴力解法
最简单的解法是暴力解法，即通过两层循环遍历所有可能的子串，然后判断每个子串是否为回文串。如果是，则更新最长回文子串的长度和起始位置。
```java
public class LongestPalindrome {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
if (isPalindrome(s, i, j) && (j - i + 1) > (end - start)) {
start = i;
end = j;
}
}
}
return s.substring(start, end + 1);
}
private boolean isPalindrome(String s, int start, int end) {
while (start < end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}
}
```
三、动态规划解法
动态规划解法通过建立一个二维数组dp，其中dp[i][j]表示字符串s从索引i到j的子串是否为回文串。根据动态规划的思想，我们可以通过以下状态转移方程来求解：
- 如果s[i] == s[j]，则dp[i][j] = dp[i + 1][j - 1]
- 否则，dp[i][j] = false
```java
public class LongestPalindrome {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int start = 0;
int end = 0;
int n = s.length();
boolean[][] dp = new boolean[n][n];
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;
start = i;
end = i + 1;
}
}
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;
start = i;
end = j;
}
}
}
return s.substring(start, end + 1);
}
}
```
四、中心扩展法
中心扩展法通过将字符串中的每个字符视为回文串的中心，然后向左右两边扩展，来判断最长回文子串。对于奇数长度的回文串，中心是一个字符；对于偶数长度的回文串，中心是两个字符。
```java
public class LongestPalindrome {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) {
return "";
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
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;
}
}
```
五、总结
本文通过分析“最长回文子串”问题，介绍了三种不同的解决方案：暴力解法、动态规划解法和中心扩展法。这些方法各有优缺点，具体选择哪种方法取决于实际需求。在实际编程过程中，我们需要根据问题的规模和复杂度来选择合适的算法。
