5. 最长回文子串

题目

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：”bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

经典动态规划题目， 表示子串是否是回文，dp二维矩阵只需要填充对角线及其上方部分，即下面有字母的部分，为T表示是回文，F表示不是。

//   c b b d
// c T F F F
// b   T T F
// b     T F
// d       T

有如下状态转移方程：

%20%3D%3D%20s.charAt(j)%20%5C%26%5C%26%20dp%5Bi%20%2B%201%5D%5Bj%20-%201%5D%2C%20j-i%3E2#card=math&code=dp%5Bi%5D%5Bj%5D%20%3D%20s.charAt%28i%29%20%3D%3D%20s.charAt%28j%29%20%5C%26%5C%26%20dp%5Bi%20%2B%201%5D%5Bj%20-%201%5D%2C%20j-i%3E2&id=YHzTQ)

%20%3D%3D%20s.charAt(j)%2C%200%3C%3Dj-i%3C%3D2#card=math&code=dp%5Bi%5D%5Bj%5D%20%3D%20s.charAt%28i%29%20%3D%3D%20s.charAt%28j%29%2C%200%3C%3Dj-i%3C%3D2&id=wynPc)

依赖，即当前位置左下角的值，因此可以从最长对角线开始从左上角到右下角斜着遍历，然后依次往上，直到右上角。

代码

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int delta = 0; delta < n; delta++) {
            for (int i = 0, j = delta; j < n; i++, j++) {
                // 只有两端字母相同才需要进一步看是否更新dp和ans
                if (s.charAt(i) == s.charAt(j)) {
                    // j - i <= 2 时不用看 dp[i + 1][j - 1]
                    dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
                    if (dp[i][j] && j - i + 1 > ans.length()) {
                        ans = s.substring(i, j + 1);
                    }
                }
            }
        }
        return ans;
    }
}