[数据结构与算法]LeetCode每日一题【blog00005】-2021/08/04 -最长回文子串

题目：5.最长回文子串

题目描述:
给你一个字符串 s，找到 s 中最长的回文子串。
注意：题目详细输入输出见官网。

来源：力扣（LeetCode）
链接：点击跳转至LeetCode原题目页面

• 算法实现如下：

public String longestPalindrome(String s) {
    int len = s.length();
    if (len <= 1) return s;

    char[] chs = s.toCharArray();
    // 状态容器
    boolean[][] dp = new boolean[len][len];

    for (int i=0; i<len; i++) {
        dp[i][i] = true;
    }

    int max = 1, start = 0;
    // 要确保 j 是外层循环
    // 如果 i 是外层循环，那么 j 循环增大，而其子串是否是回文串还不知道，就会出现错误
    for (int j=1; j<len; j++) {
        for (int i=0; i<len-1 && i<j; i++) {
            if (chs[i] != chs[j]) {
                dp[i][j] = false;
            } else {
                // 在第 1 个字符和最后 1 个字符相等的情况下，如果当前子串的长度为1, 2, 3, 则一定是回文串
                if (j-i <3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i+1][j-1];
                }
            }

            if (dp[i][j] && j-i+1 > max) {
                max = j-i+1;
                start = i;
            }
        }
    }

    return s.substring(start, start+max);
}

• 执行结果
  

算法实现思路： 动态规划