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.

对于这道题，要怎么设计这个table就是非常难想到的事情。因为要利用一个二维数组，把二维数组的两个下标作为标示主串里面的两个字符位置，实在是够难想到的了。

什么时候使用动态规划法：

Optimal substructure

Overlapping subproblems

构建解的方法：

Characterize structure of optimal solution

Recursively define value of optimal solution

Compute in a bottom-up manner

如果是用暴力法的话，就需要O(n^3) 时间效率了，但是使用动态规划法，就只需要O(n^2)的时间复杂度了。

最难想的地方：P代表一个表，比较难想的就是P表的下标i和j代表原字符串中的两个前后下标s[i]和s[j]的位置。

如果P[i,j]为真，当且仅当si-1,si-2...sj-1,sj这一个子串都为palindrome。例如：s[] = skrdjdre那么P[2][6] = true，因为s[2]=r=s[6],且djd为回文。

不明白，可以看下表，动手填一填，未填出的都初始化为false,其中t代表填写true：

下面就是实现上述思想的程序，时间复杂度O(n*n),空间复杂度O(n*n)

string longestPalindrome(string s)   
    {  
        int n = s.length();  
        vector > table;  
        vector temp(n, false);  
        for (int i = 0; i < n; i++)  
        {  
            table.push_back(temp);  
            table[i][i] = true;  
        }  
        //Attention: Don't forget we need two centor for palindrome  
        int subStartPoint = 0;  
        int maxLength = 1;  
        for (int i = 1; i < n; i++)  
        {  
            if (s[i-1] == s[i])  
            {  
                table[i-1][i] = true;  
                subStartPoint = i-1;  
                maxLength = 2;  
            }  
        }//for  
        for (int k = 3; k <= n; k++)  
        {  
            for (int i = 0; i <= n-k; i++)  
            {  
                int j=k+i-1;  
                if (s[i] == s[j] && table[i+1][j-1] == true)  
                {  
                    table[i][j] = true;  
                    if(maxLength < k)  
                    {  
                        subStartPoint = i;  
                        maxLength = k;  
                    }  
                }  
            }//for(int i = 0...  
        }//for(k=3...  
        return s.substr(subStartPoint, maxLength);  
    }

实际leetcode运行速度：

但是其实有更加简单的方法，实际运行速度更加快。

思想：

1. 以每个s[i]字符为中心，两边测试看以这个字符为中心的回文长度是多少

2. 以每两个字符s[i-1]s[i]为中心，测试这两个字符是否相等，和以这两个字符为中心的回文有多长

最后记录最大长度和最大长度子串起点

其实我觉得这个算法比前面的算法还好理解：

int testTwoSides(string &s, int low, int up)  
    {  
        int n = s.length();  
        int max = 0;  
        if (low == up)  
        {  
            low--;  
            up++;  
            max = 1;  
        }  
        while (low>=0 && up maxLength)  
            {  
                subStartPoint = i - temp/2;  
                maxLength = temp;  
            }  
        }  
        for (int i = 1; i < n; i++)  
        {  
            temp = testTwoSides(s, i-1, i);  
            if (temp > maxLength)  
            {  
                subStartPoint = i - temp/2;  
                maxLength = temp;  
            }  
        }  
        return s.substr(subStartPoint, maxLength);  
    }

理论上这个算法的时间复杂度是O(n*n)，空间复杂度O(1);

记得前段时间看到某博主对于类似的这样的算法说成时间复杂度是O(n)，所以明确说明这个时间复杂度是：O(n*n)

计算起来有点麻烦，至于是如何计算的，因为牵涉单概率论的知识和算法时间复杂度计算基础知识，虽然不算很难的概率论知识，但是不是那么容易讲明白的。怕讲不好，而且也不用那么麻烦每个算法都那么正规的分析，不然就累死人额。

所以可以对于这个算法可以给出特定例子走一走，比如对于串aaaaaaaaaaa，那么它就是最坏情况的时间复杂了。

LeetCode Longest Palindromic Substring 最长回文子字符串 两种方法分析解答