康瑞部落

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, and there exists one unique longest palindromic substring.

解题思路：

1、动态规划，找回文。用二维数组记录j到i是否为回文，若isPalin[j+1][i-1]为回文，且s[j]==s[i]，则isPalin[j][i]为回文。

class Solution {
public:
    string longestPalindrome(string s) {
        string result="";
        int len=s.length();
        if(len==0){
            return result;
        }
        int start=0, end=0;
        bool isPalin[len][len];       //i到j是否为回文
        for(int i=0; i<len; i++){
            isPalin[i][i]=true;
        }
        
        for(int i=1; i<len; i++){
            for(int j=i-1; j>=0; j--){        //计算j到i是否为回文
                if( (j==i-1&&s[j]==s[i]) || (isPalin[j+1][i-1]&&s[j]==s[i])){
                    isPalin[j][i]=true;
                    if(i-j>end-start){
                        start=j;
                        end=i;
                    }
                }else{
                    isPalin[j][i]=false;
                }
            }
        }
        
        
        result = s.substr(start, end-start+1);
        
        return result;
    }
};

此前用某个编译器不支持int array[变量]，因此每次都用new，却会报内存溢出的错误。leetcode的编译器支持int array[变量]，可以通过。

2、上述方法空间复杂度为O(n^2)，时间复杂度为O(n^2)。若以某个字符（或字符的空隙）向两边扩展统计，可以将空间复杂度降为O(1)，下面是誊抄其他人的Java代码：

public String longestPalindrome(String s) {
    if(s == null || s.length()==0)
        return "";
    int maxLen = 0;
    String res = "";
    for(int i=0;i<2*s.length()-1;i++)
    {
        int left = i/2;
        int right = i/2;
        if(i%2==1)
            right++;
        String str = lengthOfPalindrome(s,left,right);
        if(maxLen<str.length())
        {
            maxLen = str.length();
            res = str;
        }
    }
    return res;
}
private String lengthOfPalindrome(String s, int left, int right)
{
    
    while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right))
    {
        left--;
        right++;
    }
    return s.substring(left+1,right);
}

二次刷题（2015-08-17）

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if(len == 0){
            return "";
        }
        string result = "";
        
        for(int i=0; i<2*len - 1; i++){
            int left = i/2;
            int right = i/2;
            if(i%2==1){
                right++;
            }
            while(left>=0 && right < len && s[left] == s[right]){
                left--;
                right++;
            }
            string temp = s.substr(left + 1, right - left - 1);
            if(temp.length() > result.length()){
                result = temp;
            }
        }
        
        return result;
    }
};