题解 | #最长回文子串#

方法一：暴力解法

• 最直接粗暴的方法，但是时间复杂度很高。按照子串起始位置和结束位置，遍历所有可能的子串，即 left:0->n-1, right:left+1->n-1。再每次通过while循环判断该子串是否是回文串。
• 第一层循环为子串起始位置，第二层循环为子串结束位置，第三层循环为判断字符串是否为回文串。

  class Solution {
  public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        int max=1;
        for(int left=0;left<n;left++){
            for(int right=left+1;right<n;right++){
                int x=left,y=right;
                //while循环判断当前字符是否为回文串。
                while(x<=y){
                    if(A[x]==A[y])
                    {
                        x++;
                        y--;
                    }else{
                        break;
                    }
                }
                if(x>y){
                    if(right-left+1>max)
                        max=right-left+1;
                }                    
            }
        }
        return max;
    }
  };

复杂度分析：

时间复杂度：O(n^3)，两个for循环遍历起始和结束位置，一个while循环判断当前子串是否为回文串。
空间复杂度：O(1)，仅一些临时变量，常量级。

方法二：动态规划

我们在进行暴力解法时，发现有很多重复冗余的操作，又发现该问题存在最优子结构，因此可以考虑使用dp(动态规划)。
思路：使用二维数组dp，对于dp[i][j]（其中i<=j，i表示子串起始位置，j表示子串结束位置），如果dp[i][j]为1，则表明当前子串为回文串；如果为0，则表示不是回文串。其中

代码如下：

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        vector<vector<int>> dp(n,vector<int>(n));
        int ans=1;
        //l表示子串长度，i为子串起始位置
        for(int l=0;l<n;l++){
            for(int i=0;i+l<n;i++){
                int j=i+l;
                if(l==0){
                    dp[i][j]=1;
                }else if(l==1){
                    dp[i][j]=(A[i]==A[j]);
                }else{
                    dp[i][j]=(A[i]==A[j]&&dp[i+1][j-1]);
                }
                if(dp[i][j]&&l+1>ans){
                    ans=l+1;
                }
            }
        }
        return ans;
    }
};

对字符串"abba"的dp数组值分析表格如下：

复杂度分析：

时间复杂度：O(n^2)，双重循环，对二维数组dp每个访问一次。
空间复杂度：O(n^2)，二维数组dp。