93、动态规划-最长回文子串

思路

首先从暴力递归开始，回文首尾指针相向运动肯定想等。就是回文，代码如下：

public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        return longestPalindromeHelper(s, 0, s.length() - 1);
    }

  // 递归方法，用于寻找从left到right范围内的最长回文子串
    private String longestPalindromeHelper(String s, int left, int right) {
        if (left == right) {
            return s.substring(left, right + 1); // 如果左右指针相等，说明是单个字符，单个字符本身是回文
        }
        // 如果当前字符串是回文，直接返回这个子串
        if (isPalindrome(s, left, right)) {
            return s.substring(left, right + 1);
        }

        // 不是回文时，尝试两种情况：忽略左边字符或忽略右边字符
        String leftPalindrome = longestPalindromeHelper(s, left + 1, right);  // 忽略左边字符
        String rightPalindrome = longestPalindromeHelper(s, left, right - 1); // 忽略右边字符

        // 比较这两种情况，返回更长的那个回文子串
        return leftPalindrome.length() > rightPalindrome.length() ? leftPalindrome : rightPalindrome;
    }

    // 辅助方法，用于检查给定字符串s从left到right的部分是否是回文
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {  // 双指针法检查是否回文
            if (s.charAt(left) != s.charAt(right)) {
                return false; // 一旦发现不对称，立即返回false
            }
            left++;  // 移动左指针
            right--; // 移动右指针
        }
        return true; // 所有字符均对称，是回文
    }

递归面临很多重复计算，这个时候可以使用动态规划

动态规划的思路：

1. 状态定义：定义 dp[i][j] 为布尔值，表示字符串从索引 i 到索引 j 的子串是否为回文。
2. 初始化：单个字符总是回文，所以对于所有 i，dp[i][i] 是 true。
3. 状态转移方程：如果 s[i] 和 s[j] 相等，并且内部的子串也是回文（即 dp[i+1][j-1] 是 true 或者 i 和 j 之间的距离小于等于2），那么 dp[i][j] 也应该是 true。
4. 从底向上填表：由于每个状态依赖于左下方的状态（即 dp[i+1][j-1]），我们需要从下向上和从左到右填充这个表。

 public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String longest = "";

        // 填充动态规划表
        for (int len = 1; len <= n; len++) { // len 是当前子串的长度
            for (int start = 0; start < n; start++) {
                int end = start + len - 1;
                if (end >= n) { // 确保不越界
                    break;
                }
                // 设置dp[start][end]的值
                dp[start][end] = (s.charAt(start) == s.charAt(end)) && (len <= 2 || dp[start + 1][end - 1]);

                // 如果当前子串是回文，检查它是否是最长的回文
                if (dp[start][end] && len > longest.length()) {
                    longest = s.substring(start, end + 1);
                }
            }
        }
        return longest;
    }