leetcode-5-最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd" 输出: "bb"

解法一：

​ 暴力解法，通过双重循环，对每个子串进行判断，时间复杂度极高O(n^3)

bool isPalindromic(string& s,int i,int j) {//判断是否为回文 while(i<j) { if(s[i]!=s[j]) return false; i++; j--; } return true; } string longestPalindrome(string s) { if(s.length()==1) return s; int max_index_i = 0;//左下标 int max_index_j = 0;//右下标 int maxLength = 1;//最长长度 for(int i = 0;i<s.length()-1;i++) { for(int j = i+1;j<s.length();j++) { if(j-i+1>maxLength && isPalindromic(s,i,j)) {//是回文 maxLength = j-i+1; max_index_i = i; max_index_j = j; } } } // cout<<max_index_i<<endl; // cout<<max_index_j<<endl; // cout<<maxLength<<endl; return string(s,max_index_i,max_index_j-max_index_i+1); }

解法二：

​ 中心扩展方法，分为奇数扩展和偶数扩展两种情况，在外层循环中找到中心点，从这个中心点向外一层一层扩散，若这个点与其相邻的点的字符相同，则需要进行偶数扩散。时间复杂度为O(n^2)，相比解法一要快上许多。

string longestPalindrome(string s) { if(s.length()==1) return s; int begin_index = 0; int maxLength = 1; for(int i = 1;i<s.length()-1;i++) { for(int sidelength = 1;i-sidelength>=0&&i+sidelength<s.length();sidelength++) {//奇数扩散 //cout<<"奇数：("<< i-sidelength<<"<- "<<i<<" ->"<<i+sidelength<<")"<<endl; if(s[i-sidelength]==s[i+sidelength]) { if(2*sidelength+1>maxLength) { maxLength = 2*sidelength+1; //cout<<"maxLength: "<<maxLength<<endl; begin_index = i - sidelength; } } else break; } if(s[i-1]==s[i]) {//偶数扩散 for(int sidelength = 0;i-1-sidelength>=0&&i+sidelength<s.length();sidelength++) { //cout<<"偶数：("<< i-1-sidelength<<"<- "<<i<<" ->"<<i+sidelength<<")"<<endl; if(s[i-1-sidelength]==s[i+sidelength]) { if(2*sidelength+2>maxLength) { maxLength = 2*sidelength+2; //cout<<"maxLength: "<<maxLength<<endl; begin_index = i-1-sidelength; } } else break; } } } //cout<<maxLength<<endl; //cout<<begin_index<<endl; if(maxLength<2&&s[s.length()-2]==s[s.length()-1]) return string(s,s.length()-2,2); return string(s,begin_index,maxLength); }

解法三：

​ 动态规划，使用二维数组dp[i][j]标识s[i-j]是否为回文子串。

​ 状态转移方程为： dp[i][j] = (s[i]==s[j])&&((j-1-(i+1)<1)||dp[i+1][j-1])

状态转移方程意为，s[i-j]是否是回文串取决于s[(i+1)-(j-1)]是否是回文串以及第i个和第j个字符是否相同。

string longestPalindrome(string s) { int n = s.length(); if(n==1) return s; int begin_index = 0; int maxLength = 1; vector<vector<bool>> dp(n,vector<bool>(n)); for(int j = 1;j<n;j++) { for(int i = 0;i<j;i++) { if(s[i]!=s[j]) dp[i][j] = false; else { if(j-i<3||dp[i+1][j-1]) { dp[i][j] = true; if(j-i+1>maxLength) { maxLength = j-i+1; begin_index = i; } } else dp[i][j] = false; } } } return string(s,begin_index,maxLength); }