Leetcode---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.

首先我用了DP，没想到存储没报错，时间报错了，TLE了。

原理是记录所有回文，然后更新最大值。

比较值得注意的是

for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<=n-1;j++){
            dp[i][j]=dp[i+1][j-1]&&(s[i]==s[j]);

i依赖于i+1, j依赖于j-1，所以i--，j++的遍历

string longestPalindrome(string s) {
    int n=s.length();
    vector<vector<bool>> dp(n,vector<bool>(n,false));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            dp[i][j]=true;
        }
    }
    int num=1;
    int x=0;
    int y=0;
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<=n-1;j++){
            dp[i][j]=dp[i+1][j-1]&&(s[i]==s[j]);
            if(dp[i][j] && (j-i+1>num)){
                num=j-i+1;
                x=i;
                y=j;
            }
        }
    }
    return s.substr(x,num);
}

后来发现其实朴素的判断回文空间复杂性更小。其实就是从0到n-1遍历，每个节点为中心判断回文，分为奇偶两种情况，

奇数遍历：

for (int i = 1; i < s.length(); ++i){
        low = i - 1;
        high = i + 1;
        while (low >= 0 && high <s.length() && s[low] == s[high])
        {
            //是回文
            --low;
            ++high;
        }
}

偶数遍历：

for (int i = 1; i < s.length(); ++i){
        low = i - 1;
        high = i;
        while (low >= 0 && high <s.length() && s[low] == s[high])
        {
            //是回文
            --low;
            ++high;
        }
}

代码如下：

string longestPalindrome(string s) {

int start = 0;
 int maxLength = 1;
string res;

    if(s.length()==1)
       return s;
    int low, high;
    for (int i = 1; i < s.length(); ++i)
    {
        low = i - 1;
        high = i;
        while (low >= 0 && high < s.length() && s[low] == s[high])
        {
            if (high - low + 1 > maxLength)
            {
                start = low;
                maxLength = high - low + 1;
            }
            --low;
            ++high;
        }
         low = i - 1;
        high = i + 1;
        while (low >= 0 && high <s.length() && s[low] == s[high])
        {
            if (high - low + 1 > maxLength)
            {
                start = low;
                maxLength = high - low + 1;
            }
            --low;
            ++high;
        }
    }
     res = s.substr(start,maxLength);
return res;


}