leetcode 5. Longest Palindromic Substring

2017-08-10

题意

和Longest Substring Without Repeating Characters恰巧相反，计算出重复字符串的最长回文子串。并返回首个最长重复子串。

我的思路及代码

暴力法：顾名思义遍历所有子串，判断是否为回文字符串。以下是我的暴力代码，遍历子串效率为O(n^2)，判断是否为回文字符串效率为O(n),所以总体效率为O(n^3)

public class Solution {
    public String longestPalindrome(String s) {
       if(s==null||s.equals(""))  return s;
       int start=0,end=1;
       for(int i=0;i<s.length()-1;i++){
           if(s.length()-i<end-start)
               break;
           for(int j=s.length()-1;j>=i+1;j--){
               if(s.charAt(i)==s.charAt(j)){
                    if(isHui(s.substring(i+1,j))){
                        if((j-i+1)>(end-start)) {
                            start = i;
                            end = j+1;
                        }
                        break;
                    }
               }
           }
       }
        return s.substring(start,end);
    }
    public boolean isHui(String str){
        if(str.equals("")||str.length()==1) return true;
        for(int m = 0;m<str.length()/2;m++){
            if(str.charAt(m)!=str.charAt(str.length()-m-1))
                return false;
        }
        return true;
    }
}

注意内部循环是从尾部向前遍历的。如果是

动态规划：暴力法中其实很多判断回文字符串是重复的，怎么来优化呢。可以提供一个二维数组来记录是否为回文字符串的状态。需要O(n^2)空间状态。

因为回文字符串的子字符串也是回文串。s[i,j]是回文，s[i+1,j-1]肯定也是回文

首先定义状态方程和转移方程：

P[i,j]=false:表示子串[i,j]不是回文串。P[i,j]=true:表示子串[i,j]是回文串。

P[i,i]=true:当且仅当P[i+1,j-1] = true && (s[i]==s[j]）

我想到了用动态规划来做，但是没想出来是因为思维固化了。固化的地方，一直想不明白遍历字符串的时候，内部字符串是否为回文串，没法在之前的循环遍历中确定，实际上只需要换一种遍历方式即可，这种遍历方式是以回文串的长度，由短及长，这样在遍历到长的回文串时可以用短的回文串状态来判断。

public static String findLongestPalindrome1(String s){
        int len = s.length();
        int start = 0;
        int maxlength = 0;
        boolean p[][] = new boolean[s.length()][s.length()];
        // 子串长度为1和为2的初始化
        for(int i = 0; i < len; i++){
            p[i][i] = true;
            if(i < len - 1 && s.charAt(i) == s.charAt(i + 1)){
                p[i][i + 1] = true;
                start = i;
                maxlength = 2;
            }
        }
        // 使用上述结果可以dp出子串长度为3~len -1的子串
        for(int strlen = 3; strlen < len; strlen ++){
            for(int i = 0; i <=len - strlen; i++){
                int j = i + strlen - 1; // 子串结束的位置
                if(p[i + 1][j - 1] && s.charAt(i) == s.charAt(j)){
                    p[i][j] = true;
                    maxlength = strlen;
                    start = i;
                }
            }
        }
        if(maxlength > 0)
            return s.substring(start, start + maxlength);
        return null;
    }

中心扩展法
中心扩展就是把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。
但是要考虑两种情况：
1、像aba，这样长度为奇数。
2、像abba，这样长度为偶数。

public static String findLongestPalindrome2(String s){
        int len = s.length();
        int maxlength = 0;
        int start = 0;
        // 类似于aba这种情况，以i为中心向两边扩展
        for(int i = 0; i < len; i++){
            int j = i - 1;
            int k = i + 1;
            while(j >= 0 && k < len && s.charAt(j) == s.charAt(k)){
                if(k - j + 1 > maxlength){
                    maxlength = k - j + 1;
                    start = j;
                }
                j --;
                k ++;
            }
        }
        // 类似于abba这种情况，以i，i+1为中心向两边扩展
        for(int i = 0; i < len; i++){
            int j = i;
            int k = i + 1;
            while(j >= 0 && k <len && s.charAt(j) == s.charAt(k)){
                if(k - j + 1 > maxlength){
                    maxlength = k - j + 1;
                    start = j;
                }
                j --;
                k ++;
            }
        }
        if(maxlength > 0)
            return s.substring(start, start + maxlength);
        return null;
    }