05 LongestPalindromicSubstring

ref :5 Longest Palindromic Substring

Given a strings, 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"

分析&代码

方法一

先上代码好了

public String longestPalindrome(String s) {
    if(s == null || s.length() == 0) {
        return "";
    }
    int maxLen = Integer.MIN_VALUE;
    String maxStr = "";
    int len = s.length();
    boolean[][] dp = new boolean[len][len];
    for(int l = 0; l < len; l++) {
        for(int start = 0; start + l < len; start++) {
            int end = l + start;
            if((l < 2 || dp[start + 1][end - 1]) && s.charAt(start) == s.charAt(end)) {
                dp[start][end] = true;
                if(l > maxLen) {
                    maxLen = l;
                    maxStr = s.substring(start, end + 1);
                }
            }
        }
    }
    return maxStr;
}

用dp做，状态转移方程是dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]

初始化是：

• 每单个字母的都是Palindrome，所以所有dp[i][i]都是true
• 每相邻的两个[i][i+1]取决于s[i]是否等于s[i+1]

需要注意的是：

外层循环length的时候，值是从[0,s.length-1].因为可以想一下，如果单个字母的表示是dp[i][i],这个palindrome的长度其实是1，但是i和j相减是0.另个就是如果整串都是palindrome,是dp[0][n-1],其实长度是N，但是坐标相减是n-1，这里要注意

方法二

准备亚麻的时候突然发现自己习惯的做法不是最优解

还是先上代码：

public String longestPalindrome(String s) {
    if(s == null || s.length() < 2) {
        return s;
    }
    int[] res = new int[2];
    for(int i = 0; i < s.length() - 1; i++) {
        expandPalindrome(s, i, i, res);//len == odd
        expandPalindrome(s, i, i + 1, res);//len == even
    }
    return s.substring(res[1], res[0] + res[1]);
}

private void expandPalindrome(String s, int left, int right, int[] res) {
    while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    if(res[0] < right - left - 1) {
        res[0] = right - left - 1;
        res[1] = left + 1;
    }
}

res[0]表示maxLen,res[1]表示start