leetcode 每日打卡————「5. 最长回文子串」

题目点击这里 ➡️「最长回文子串」

思路：

首先考虑如何判断某字符串是否为回文子串？

1、若字符串长度为 1，则是回文子串；

2、若字符串长度为 2，则考虑两个字符是否相等；

3、长度大于 2 时，需要考虑的是，首尾两个字符是否相等，同时去掉首尾后剩下的便是其子串（也需要是回文串）。

public String longestPalindrome(String s) {
        int result = 1, start = 0;
        int len = s.length();
        if (len == 1) {
            return s;
        }
        boolean[][] dp = new boolean[len][len];
        // 单个字符都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        // 子串长度为 1 已经考虑过了，所以从 2 开始
        for (int childLen = 2; childLen <= len; childLen ++) {
        	// 左边界为 i
            for (int i = 0; i <= len - childLen; i ++) {
            	// j 为右边界，dp[i][j] 代表字符串 s[i:j] 是否为回文串
                int j = i + childLen - 1;
                // 超过字符串最大长度
                if (j >= len) {
                    break;
                }
                if (j - i + 1 == 2) {
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                	// 字符串是否为回文串的判断条件
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }
                // 每次更新结果
                if (dp[i][j] && j - i + 1 > result) {
                    result = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substring(start, start + result);
    }