难度: Medium

内容描述

给定一个字符串s，找出s中最长的回文子字符串。你可以假设s的最大长度为1000。
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"

解题方案

思路 1
**- 时间复杂度: O(n^2)**- 空间复杂度: O(n^2)**

使用动态规划的思路,用一个二维数组cache[i][j]记录i到j是否为回文串, beats 54.36%

class Solution {
    // 采用动态规划
    // 如果 i == j ，则只有一个字母 肯定是回文串
    // 如果 char[i] == char[j] && j == i + 1 , 两个字母相等 肯定是回文串
    // 如果 char[i] == char[j] && j > i + 1 && cache[i+1][j-1]为true，则肯定是回文串
    public String longestPalindrome(String s) {
        if(s == null || s.length() <2){
            return s;
        }
        boolean[][] cache = new boolean[s.length()][s.length()]; // 记录 i ~ j 是否是回文串
        char[] chars = s.toCharArray();
        int len = s.length();
        int start = 0;
        int end = 0;
        // 采用至底向上的动态规划，也可以采用递归方式
        for(int i = len - 1; i >= 0; i --){
            for(int j = i; j < len; j ++){
                if(i == j){
                    cache[i][j] = true;    
                }else if(j == i + 1 && chars[i] == chars[j]){
                    cache[i][j] = true;
                    if(end - start + 1 < 2){
                        end = j;
                        start = i;
                    }
                }else if(chars[i] == chars[j] && cache[i + 1][j-1]){
                    cache[i][j] = true;
                    if(end - start  < j-i){
                        start = i;
                        end = j;
                    }
                }else{
                    cache[i][j] = false;
                }
            }
        }
        return s.substring(start,end+1);
    }
}