題目

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

思路

毫無疑問是動態(tài)規(guī)劃了。用二維數(shù)組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]

根據(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;
    }