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:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
 
Example:
Input: "cbbd"
Output: "bb"

Solution:

下面是超时的答案：

image.png

class Solution {
    String s;
    int len;
    public String longestPalindrome(String s) {
        if(s == null) {
            return null;
        }
        this.s = s;
        this.len = s.length();
        if(len == 0) {
            return "";
        }
        int max = 1;
        int start = 0;
        int end = 0;
        for(int step = 1; step < len; step++) {
            for(int i = 0; i < len - step; i++) {
                if(isPalin(i, i + step)) {
                    int temp = step + 1;
                    if(temp > max) {
                        max = temp;
                        start = i;
                        end = i + step;
                    }
                }
            }
        }
        return s.substring(start, end + 1);
    }
    
    private boolean isPalin(int l, int r) {
        int i = l; 
        int j = r;
        while(i <= j) {
            if(s.charAt(i) != s.charAt(j)) {
                return false;
            } else {
                i++;
                j--;
            }
        }
        return true;
    }
}

改进答案：

class Solution {
    String s;
    public String longestPalindrome(String s) {
        this.s = s;
        if(s == null) {
            return null;
        } else if(s == "") {
            return "";
        }
        int max = 1;
        int left = 0; 
        int right = 0;
        int n = s.length();
        int[][] f = new int[n][n];
        for(int i = 0; i < n; i++) {
            f[i][i] = 1;
        }
        for(int i = 0; i < n - 1; i++) {
            if(isPalin(i, i + 1)) {
                f[i][i + 1] = 1;
                max = 2;
                left = i;
                right = i + 1;
            } else {
                f[i][i + 1] = 0;
            }
        }
        for(int step = 2; step < n; step++) {
            for(int i = 0; i < n - step; i++) {
                if(f[i + 1][i + step - 1] == 1) {
                    if(s.charAt(i) == s.charAt(i + step)) {
                        left = i;
                        right = i + step;
                        f[i][i + step] = 1;
                    } else {
                        f[i][i + step] = 0;
                    }
                } else {
                    f[i][i + step] = 0;
                }
            }
        }
        return s.substring(left, right + 1);
    }
    
     private boolean isPalin(int l, int r) {
        int i = l; 
        int j = r;
        while(i <= j) {
            if(s.charAt(i) != s.charAt(j)) {
                return false;
            } else {
                i++;
                j--;
            }
        }
        return true;
    }
}

思路：
比如判断三个字符的字符串是回文：当且仅当中间一个是回文（显然是），然后左边一个字符等于右边一个字符；判断四个字符，当且仅当中间两个是会问的，且最左边和最右边的字符相等；判断五个字符，当且仅当中间三个字符是回文串，且最左边的字符等于最右边的字符……