5. Longest Palindromic Substring

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

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

Example 2:

Input: "cbbd"
Output: "bb"

ps:这里是求substring ，而不是subsequence

solution1:Time Limit Exceeded

其实这也是一个动态规划的问题，对于每个子问题都会进行深度优先搜索，时间复杂度太大，没有ac?

public String longestPalindrome(String s) {
        int start = 0;
        int end = 0;
        int longestLen = 0;
        if(s == null || s.length() < 2) return s;


        int len = s.length();
        for(int j = 1; j <= len - 1; j++){
            for(int i = 0; i < j; i++){
                if(isPalindrome(s.substring(i,j+1))){
                    if(j - i + 1 > longestLen){
                        longestLen = j - i +1;
                        start = i;
                        end = j;
                    }
                }

            }
        }
        return s.substring(start,end+1);

    }

    public boolean isPalindrome(String s){
        int start = 0;
        int end = s.length() - 1;
        if(s.length() == 1 ) return true;

        if(s.charAt(start) == s.charAt(end) ){
            if(end - start <= 2)
                return true;
            return isPalindrome(s.substring(start+1,end));
        }else {
            if(end - start == 1)
                return false;
        }

        return false;

    }

• s.length() not s.length
• s.substring(start,end):start is inclusive, end is exclusive

solution2动态规划的改进版——构建辅助数组

每求解一个字串是否为palindrome时就记录下来，下次需要使用的时候可以直接拿来用，而不是又重新求解

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() < 2) return s;

        int len = s.length();

        boolean[][] isPalindrome = new boolean[len][len];

        int maxLen = 0;
        int left = 0;
        int right = 0;

        //先初始化对角线的值
        for(int i = 0; i < len; i++){
            isPalindrome[i][i] = true;
        }

        //这里从右下角而不是左下角开始，因为这样才是自底向上的
        for(int start = len - 2; start >= 0; start--){
            for(int end = start + 1; end < len; end++){
               if(s.charAt(start) == s.charAt(end)){
                    if(end - start == 1)
                        isPalindrome[start][end] = true;
                    else
                        isPalindrome[start][end] =  isPalindrome[start+1][end-1];
                    
                }
                if(isPalindrome[start][end]){
                    if( end - start + 1 > maxLen){
                        maxLen = end - start + 1;
                        left = start;
                        right = end;
                    }


                }
            }
        }


        return s.substring(left,right+1);
    }

}

参考
https://www.youtube.com/watch?v=0xeBqanD5GQ