最长回文子串java

最长回文子串是指一个字符串中的最长回文子串。在 Java 中，可以使用动态规划的方法来解决这个问题。

首先，定义一个二维数组 dp[][]，其中 dp[i][j] 表示字符串从索引 i 到 j 的子串是否是回文子串。初始化时，将所有 dp[i][i] 设置为 true，表示单个字符是回文子串。

然后，通过遍历字符串的长度和起始索引来更新 dp[][] 数组。具体的更新规则如下：

1. 当 s.charAt(i) == s.charAt(j) 且 (j - i <= 2 || dp[i+1][j-1] == true) 时，dp[i][j] 也为 true。这意味着如果当前字符相等，并且子串长度小于等于2或者去掉首尾字符后的子串是回文子串，则当前子串也是回文子串。
2. 在更新 dp[][] 数组的过程中，记录最长回文子串的起始索引和长度。

以下是使用动态规划解决最长回文子串问题的 Java 代码示例：

public class LongestPalindromeSubstring {
    public static String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int maxLength = 1;
        int start = 0;
        
        // 初始化单个字符为回文子串
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        
        // 更新 dp[][] 数组并记录最长回文子串的起始索引和长度
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && (len <= 2 || dp[i+1][j-1])) {
                    dp[i][j] = true;
                    if (len > maxLength) {
                        maxLength = len;
                        start = i;
                    }
                }
            }
        }
        
        return s.substring(start, start + maxLength);
    }
    
    public static void main(String[] args) {
        String s = "babad";
        String longestPalindrome = longestPalindrome(s);
        System.out.println("最长回文子串为: " + longestPalindrome);
    }
}

运行上述代码，输出结果为：

最长回文子串为: bab

以上就是使用动态规划解决最长回文子串问题的 Java 实现方法。希望能对你有所帮助！