LeetCode | Longest Palindromic Substring

本文主要是介绍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.

最长回文串问题，网上也有超多的教程…
我就不班门弄斧了，只写一点自己的写作思路好了

思路

暴力解法

从第一位开始遍历，每次设置遍历区域为当前到最后一位，再判断这个区域是否回文，O(n^3)。在提交之前就被我否决了

从中间扩展

在上一种方法中，回文串的特殊规律没有被很好地利用。即回文串是两边对等的。所以可以从中间任意一点出发向两头扩展，这样可以在O(n)的时间内得到这一点的回文串最长长度。
整体复杂度O(n^2) 空间复杂度O(1)

动态规划

使用动态规划的思路，dp[i][j]表示i~j是否为回文字符串。

dp[i][j]为回文串，当且仅当：
i==j
i+1==j && s[i]==s[j]
dp[i+1][j-]为回文串并且 s[i]==s[j]

无后效性 设有回文串i~j，那么i-1~j+1串是否为回文串，不受i+1~j-1串的影响。它只与当前状态i~j有关
最优子结构 要求出最长回文子串dp[i][j]，那么每部分（dp[i-1][j-1]开始）都必须是回文子串

class Solution {
public://动态规划法 时间O(n^2) 空间O(n^2)
//     string longestPalindrome(string s) {
//         int n=s.size();
//         int dp[n][n];
//         memset(dp,0,sizeof(dp));
//         for(int i=0;i<n;i++) dp[i][i]=1;//      for(int i=n-1;i>=0;i--){
//          for(int j=i+1;j<n;j++){
//              if(s[i]==s[j]){
//                  if(j==i+1) dp[i][j]=1;
//                  else dp[i][j]=dp[i+1][j-1];
//              } 
//          }
//      }
//      int max=0;
//      string target="";
//      for(int i=0;i<n;i++){
//          for(int j=i;j<n;j++){
//              if(dp[i][j]>0 && j-i+1>max)
//              {
//                  max=j-i+1;
//                  target=s.substr(i,j-i+1);
//              }
//          }
//      }
//         return target;
//     }//由中间扩展，时间O(n^2) 空间O(1)string longestPalindrome(string s) {int n=s.size();if(n==1) return s;string target("");for(int i=0;i<n;i++){//这样似乎是O(n^3)复杂度// for(int j=1;j<=1000 && i+j<n;j++){//     if(isReverse(s,i,i+j)){//         if(j>longest){//             longest=j;//             target=s.substr(i,i+j);//         }//     }// }int length=0,left=i,right=i;//尝试从第i个出发，往两边扩展if(i>0 && s[i]==s[i-1]){//如果是这种，有可能是abba类型的left=i-1;printf("possible");target=updateTarget(s,length,left,right,target);}//普通的类型，比如aba//所有的都应当执行一下这种length=-1,left=i,right=i;target=updateTarget(s,length,left,right,target);}return target;}//更新最长子串的函数，从left和right出发向两侧寻找string updateTarget(string s,int length,int left,int right,string target){int n=s.size();while(s[left]==s[right]){length+=2;if(left==0 || right==n-1) break;left--;right++;}if(s[left]!=s[right]){left++;right--;}if(right-left+1>target.size()){int longest=right-left+1;target=s.substr(left,longest);}return target;}
};

另外记录一下之前自己错误的思路

        //这是一个自以为正确的dp//我以dp[i][j]保存了二者之间的最长长度//dp[i][j]=dp[i+1][j-1]+2  or   max(dp[i][j-1],dp[i+1][j]);//但是这是有问题的。//我们不能知道s[i]==s[j]的情况下，它是否是回文串//所以dp[i][j]应当保存i~j是否为回文，而其长度可以直接得出 
//      for(int i=0;i<n;i++) dp[i][i]=1;
//      
//      for(int i=n-1;i>=0;i--){
//          for(int j=i+1;j<n;j++){
//              if(s[i]==s[j])
//              dp[i][j]=dp[i+1][j-1]+2;
//              else 
//              dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
//          }
//      }
//      int max=1;
//      for(int i=0;i<n;i++){
//          for(int j=0;j<n;j++){
//              if(dp[i][j]>max) max=dp[i][j];
//          }
//      }
//      printf("max %d\n",max);