Question

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

My Answer 1

暴力求解，超时，时间复杂度 O(n^3)

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String maxStr = "";
        for(int i = 0; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                String temp = s.substring(i,j);
                if(isPalindromic(temp) && temp.length() > maxStr.length()) {
                    maxStr = temp;
                }
            }
        }
        return maxStr;
    }
    
    // 字符串是否回归
    private boolean isPalindromic(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
}

My Answer2

动态规划 O(n^2)

class Solution {
    
    // 动态规划, 避免做重复运算，已经算过的直接拿来用
    public String longestPalindrome(String s) {
        int n = s.length();
        String res = "";

        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // 情况1：如果i和j字符相同，且子串长度小于等于3，则一定是回归串；如 a，aa，aba
                // 情况2：如果i和j字符相同，且 (i+1,j-1) 的子串也是回文串，则一定是回文串 如 abcba, 当前 i=0,j=5
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]);
                
                if (dp[i][j] && (res == null || j - i + 1 > res.length())) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }
    
}