题目

https://leetcode.com/problems/longest-palindromic-substring/submissions/

思路

毫无疑问是动态规划了。用二维数组dp[i][j]记录从i下标到j下标是否为回文子串，则dp[i][j]取值有下面三种情况：

• i==j，此时dp[i][j]=true
• i+1=j，此时dp[i][j]=s[i]==s[j]
• 其余情况，此时dp[i][j]取值为true的条件为：dp[i+1][j-1]=true并且s[i]==s[j]

根据条件直接遍历len就好

代码

    public String longestPalindrome(String s) {
        int length = s.length();
        boolean[][] isPal = new boolean[length][length];
        int maxLen = 0;// 记录最长的长度
        String answer = ""; // 记录最长的字符串

        // 遍历子串的长度
        for(int len = 1; len <= length; len++) {
            for (int startIndex = 0; startIndex < length; startIndex++) {
                //计算起始位置并确保位置合法
                int endIndex = startIndex + len - 1;
                if (endIndex >= length) {
                    break;
                }
                // 核心逻辑
                isPal[startIndex][endIndex] = (len == 1)  // 长度为1
                        || (len == 2 && s.charAt(startIndex) == s.charAt(endIndex)) // 长度为2
                        || (isPal[startIndex + 1][endIndex - 1] && s.charAt(startIndex) == s.charAt(endIndex)); // 其他情况

                if (isPal[startIndex][endIndex] && len > maxLen) {
                    maxLen = len;
                    answer = s.substring(startIndex, endIndex + 1);
                }
            }
        }

        return answer;
    }