怎么用Java找到最长回文子串

1、理解回文串

回文串是指正读和反读都一样的字符串，例如"level"、"noon"。

为了找到最长的回文子串，我们需要遍历所有可能的子串，判断其是否为回文串，并记录最长的回文子串。

2、暴力破解法

一种简单的方法是使用暴力破解法，遍历所有的子串，逐个判断是否为回文串，记录最长的回文子串。

具体步骤如下：

public String longestPalindrome(String s) {
    int maxLength = 0;
    String longest = "";
    for (int i = 0; i < s.length(); i++) {
        for (int j = i + 1; j <= s.length(); j++) {
            String substring = s.substring(i, j);
            if (isPalindrome(substring) && substring.length() > maxLength) {
                maxLength = substring.length();
                longest = substring;
            }
        }
    }
    return longest;
}

private boolean isPalindrome(String s) {
    int i = 0;
    int j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

上述代码中，我们使用了两个嵌套的循环来遍历所有可能的子串，然后使用isPalindrome方法判断子串是否为回文串。如果是回文串且长度大于最长回文子串的长度，则更新最长回文子串的长度和内容。

3、动态规划法

暴力破解法的时间复杂度为O(n^3)，效率较低。我们可以使用动态规划来优化算法。

具体步骤如下：

public String longestPalindrome(String s) {
    int maxLength = 1;
    int start = 0;
    boolean[][] dp = new boolean[s.length()][s.length()];
    for (int i = 0; i < s.length(); i++) {
        dp[i][i] = true;
        if (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
            dp[i][i + 1] = true;
            maxLength = 2;
            start = i;
        }
    }
    for (int len = 3; len <= s.length(); len++) {
        for (int i = 0; i <= s.length() - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                maxLength = len;
                start = i;
            }
        }
    }
    return s.substring(start, start + maxLength);
}

在上述代码中，我们使用一个二维数组dp来记录子串是否为回文串。dp[i][j]代表s中从索引i到索引j的子串是否为回文串。我们初始化对角线上的元素为true，表示单个字符肯定是回文串。然后，我们再判断长度为2的子串是否为回文串。接着，我们从长度为3的子串开始，判断子串的头尾字符是否相等，且中间部分是否为回文串。如果满足条件，则更新dp[i][j]为true，并记录最长回文串的长度和起始位置。

这种方法的时间复杂度为O(n^2)，效率较高。