/* * 感觉是最优解了,还有更好的解法求告知 */ private int left, maxLen; public String longestPalindrome(String s) { if (s == null || s.length() < 2) return s; for (int i = 0; i < s.length() - 1; i++) { //考虑两种情况:1.中间是bab;2.中间是bb; findMaxPalindrome(s, i, i); findMaxPalindrome(s, i, i + 1); } return s.substring(left, left + maxLen); } private void findMaxPalindrome(String s, int i, int j) { while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) { i--; j++; } if (maxLen < j - i - 1) { left = i+1; maxLen = j - i - 1; } }
/**思路:
* 从回文串的对称点开始,依次向左向右比较,不相同的时候停止遍历,直到找出最大的长度的回文子串。
* (1)回文子串长度为奇数:对称点只有一个字符
* (2)回文子串长度为偶数:对称点有两个字符
* 时间复杂度为O(n^2):对称点的数量为O(n),每次查找的时间也为O(n),所有总时间复杂度为O(n^2) */
class Solution { public: string longestPalindrome(string s) { //字符串的长度 int len = s.size(); if (len == 0) return s; //保留最长回文串 string resultStr = ""; //回文子串长度为奇数,:对称点只有一个字符的情况 for (int i=0; i<len; ++i){ // i 为对称点 int left = i;//左 int right = i;//右 //向左向右遍历,直到发现不相同的时候停止 while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){ --left; ++right; } //比较,更新最长回文串 if (right - left + 1 > resultStr.size()){ resultStr = s.substr(left, right - left + 1); } } //回文子串长度为偶数:对称点有两个字符 for (int i = 0; i < len - 1; ++i){ if (s[i] == s[i+1]){//两个对称点相同,才有继续遍历的意义 int left = i; int right = i+1; //向左向右遍历,直到发现不相同的时候停止 while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]){ --left; ++right; } //比较,更新最长回文串 if (right - left + 1 > resultStr.size()){ resultStr = s.substr(left, right - left + 1); } } } return resultStr; } };
/* * 目的:求最大回文子串 * 方法:动态规划 */ string longestPalindrome(string s) { int n = s.size(); vector<vector<bool>>dp(n,vector<bool>(n,false)); int maxVal = 1; int pos[2]={0,0}; for (int j = 0; j< s.size();++j){ dp[j][j] = true; for (int i = 0;i<j;++i) { dp[i][j] = (s[i]==s[j] &&(j-i<=2 || dp[i+1][j-1])); if(dp[i][j] && (j-i+1 > maxVal)) { pos[0] = i; pos[1] = j; maxVal = j-i+1; } } } return s.substr(pos[0],pos[1]-pos[0]+1); }
string longestPalindrome(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n, 0));
//用下标来记录,防止出现单一回文情况
int max_len = 1; //保存最长回文子串长度
int start = 0; //保存最长回文子串起点
for (int i = 0; i < n; i++)
dp[i][i] = 1;
for (int j = 1; j < n; j++) // 子串结束位置for (int i = j - 1; i >= 0; i--) { // 子串开始位置
if (j - i < 2)
dp[i][j] = (s[i] == s[j]);
else
dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);
// 保存子串
if (dp[i][j] && (j - i + 1) >= max_len) {
max_len = j - i + 1;
start = i;
}
}
return s.substr(start, max_len);
}
bool isPalindrome1(string s){
return s == string(s.rbegin(), s.rend());
}
void dfsPalindrome(string s, string &res){
if(s == "")
return ;
for (int i = 1; i <= s.size(); ++i) {
string temp = s.substr(0, i);
if(isPalindrome1(temp)){
if(temp.size() > res.size())
res = temp;
dfsPalindrome(s.substr(i), res);
}
}
}
string longestPalindrome(string s) {
string res;
dfsPalindrome(s, res);
return res;
}
//复杂度应该是o(n)吧 public class Solution { public String longestPalindrome(String s) { int[] p; StringBuilder sb = new StringBuilder(); sb.append('$'); sb.append('#'); for(int i=0;i<s.length();i++){ sb.append(s.charAt(i)); sb.append('#'); } int mx=0; int ans=0; int id=0; p=new int[sb.length()]; for(int i=1;i<sb.length();i++){ if(mx>i){ p[i]=Math.min(p[2*id-i], mx-i); }else p[i]=1; while(i+p[i]<sb.length()&&i-p[i]>=0&&sb.charAt(i-p[i])==sb.charAt(i+p[i])){ p[i]++; } if(p[i]+i>mx){ id=i; mx=p[i]+i; } ans = Math.max(ans, p[i]); } int max=0; int k=0; for(int i=0;i<p.length;i++){ if(p[i]>max){ k=i; max=p[i]; } } StringBuilder sb1= new StringBuilder(); for(int i=k-max+1;i<k+max-1;i++){ if(sb.charAt(i)!='#'&&sb.charAt(i)!='$'){ sb1.append(sb.charAt(i)); } } return sb1.toString(); } }
//中心扩散 class Solution { public: string longestPalindrome(string s) { int n = s.size(); if(n <= 1) return s; int start = 0, maxlen = 0; for(int i = 1; i < n; ++i) { //寻找以i-1,i为中点偶数长度的回文 int low = i-1, high = i; while(low >= 0 && high < n && s[low] == s[high]) { low --; high ++; } if(high - low - 1 > maxlen) { maxlen = high - low - 1; start = low + 1; } //寻找以i为中心的奇数长度的回文 low = i-1, high = i+1; while(low >=0 && high < n && s[low] == s[high]) { low --; high ++; } if(high - low - 1 > maxlen) { maxlen = high - low - 1; start = low + 1; } } return s.substr(start, maxlen); } }; // dp记录子串是否是回文串 class Solution { public: string longestPalindrome(string s) { int n = s.size(); if(n <= 1) return s; vector<vector<int>> dp(n, vector<int>(n,0)); int start = 0, ends = 1; for(int i = 0; i < n; ++i) { dp[i][i] = 1; // 一个字母的情况 if(s[i] == s[i+1] && i != n-1) // 两个字母相等的情况 { dp[i][i+1] = 1; start = i; ends = 2; } } for(int i = 3; i <= n; ++i) // 子串的长度 { for(int j = 0; j + i - 1 < n; ++j) { int k = j + i -1; if(s[j] == s[k] && dp[j+1][k-1] == 1) { dp[j][k] = 1; start = j; ends = i; } } } return s.substr(start,ends); } };
public String longestPalindrome(String s) { int maxlength = 0; int start = 0; int end = 1; for(int i=0; i<s.length(); i++){ for(int j=0; j<2; j++){ //以i为中心的情况,和以i, i+1为中心的情况 int left = i; int right = i+j; if(right == s.length()) break; while(left >= 0 && right <s.length() && s.charAt(left) == s.charAt(right)){ left--; right++; } left ++; if(maxlength < right - left){ maxlength = right-left; start = left; end = right; } } } return s.substring(start, end); }
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool> >dp(s.length(),vector<bool>(s.length(),false));
int left=0,right=0;
for(int i=0;i<s.length();++i){
for(int j=i;j>=0;--j){
if(s[i]==s[j] && (i-j<2 || dp[j+1][i-1]==true)){
dp[j][i]=true;
if(i-j>right-left){
left=j;
right=i;
}
}
}
}
return s.substr(left,right-left+1);
}
};
//利用马拉车算法进行求解 //有关动态规划,中心扩散法,以及马拉车算法的理解可参考我的博客 //http://www.cnblogs.com/pathjh/p/8798277.html import java.util.*; public class Solution { public String longestPalindrome(String s) { if(s.length()<2) return s; int[]p; StringBuilder sb=new StringBuilder(); //对字符串进行预处理 sb.append('$'); sb.append('#'); for(int i=0;i<s.length();i++){ sb.append(s.charAt(i)); sb.append('#'); } p=new int[sb.length()]; int mx=0,id=0; int resLen=0,resCenter=0; for(int i=1;i<sb.length();i++){ p[i]=i<mx?Math.min(p[2*id-i],mx-i):1; while(i+p[i]<sb.length()&&i-p[i]>=0&&sb.charAt(i+p[i])==sb.charAt(i-p[i])) p[i]++; if(mx<i+p[i]){ mx=i+p[i]; id=i; } if(resLen<p[i]){ resLen=p[i]; resCenter=i; } } //一趟循环下来后,此时resLen对应的为最长的回文子串的半径长度,resCenter对应的是最长回文子串的中心位置 StringBuilder sb1=new StringBuilder(); for(int i=resCenter-resLen+1;i<=resCenter+resLen-1;i++){ if(sb.charAt(i)!='#'&&sb.charAt(i)!='$') sb1.append(sb.charAt(i)); } return sb1.toString(); } }
class Solution { public: string longestPalindrome(string s) { if(s.size()<=1) return s; int min_s = 0, max_l = 1; int n = s.length(); for(int i=0;i<n;) { if(n-i <= max_l/2) break; int j=i,k=i; while(k<n-1 && s[k]==s[k+1]) k++; i = k+1; while(j>0 && k<n-1 && s[j-1]==s[k+1]) { k++; j--; } int new_l = k-j+1; if(new_l > max_l) { max_l = new_l; min_s = j; } } return s.substr(min_s,max_l); } };
//大家好,我是yishuihan public class Solution { public String longestPalindrome(String s){ int maxLeft=0; int maxRight=0; int max=1; int n=s.length(); for(int i=0;i<n;i++) { //偶数长度的回文子串 int start=i; int end=i+1; int len=0; //left、right是为了防止越界 int left=start; int right=end; while(start>=0&&end<n) { if(s.charAt(start)==s.charAt(end)) { len=len+2; left=start; right=end; start--; end++; } else break; } if(len>max){ maxLeft=left; maxRight=right; max=len; } //奇数长度的回文子串 start=i-1; end=i+1; len=1; left=start; right=end; while(start>=0&&end<n){ if(s.charAt(start)==s.charAt(end)) { len=len+2; left=start; right=end; start--; end++; } else break; } if(len>max){ maxLeft=left; maxRight=right; max=len; } } return s.substring(maxLeft, maxRight+1); } }
class Solution { public: // 最长回文串,使用dp string longestPalindrome(string str) { int n = str.length(); if(n==0) return ""; bool dp[n][n]; fill_n(&dp[0][0],n*n,false); int left=0,right=0,maxLen = 0; for(int j=0;j<n;j++) { dp[j][j] = true; for(int i=0;i<j;i++) { dp[i][j] = (str[i] == str[j] && (j-i < 2 || dp[i+1][j-1])); if(dp[i][j] && (j-i+1 > maxLen)) { left = i; right = j; maxLen = j-i+1; } } } return str.substr(left,right-left+1); } };
//中心拓展法 public class Solution { /** * * @param s string字符串 * @return string字符串 */ public String longestPalindrome (String s) { // write code here if(s==null || s.length()==0) return s; int index=0; int max=0; for(int i=0;i<s.length();i++){ if(max<maxLengthOfPalindrome(s,i,i)){ index=i; max=maxLengthOfPalindrome(s,i,i); } if(max<maxLengthOfPalindrome(s,i,i+1)){ index=i; max=maxLengthOfPalindrome(s,i,i+1); } } if(max%2==1) return s.substring(index-max/2,index-max/2+max); else return s.substring(index+1-max/2,index+1+max/2); } private int maxLengthOfPalindrome(String s, int i, int j){ int res=(i==j)?-1:0; while(i>=0 && j<s.length()){ if(s.charAt(i)==s.charAt(j)){ res+=2; i--; j++; }else{ break; } } return res; } }
解决思路
把输入取逆序,然后和原输入求最长子序列。
public class Solution { public static String longestPalindrome (String s) { int n = s.length(); char[] a = s.toCharArray(); char[] b = new char[n]; for (int i = 0; i < n; i++) b[i] = a[n - i - 1]; int[][] ans = new int[n + 1][n + 1]; for (int i = 0; i < n + 1; i++) { ans[0][i] = 0; ans[i][0] = 0; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { ans[i + 1][j + 1] = b[i] == a[j] ? ans[i][j] + 1 : Math.max(ans[i][j + 1], ans[i + 1][j]); } } int num = ans[n][n]; System.out.println(ans[n][n]); char[] end = new char[num]; int i = n, j = n, flag = num; while (flag > 0){ if (ans[i][j] == flag && b[i - 1] == a[j - 1]){ end[flag - 1] = b[i - 1]; i--; j--; flag--; } else if (ans[i - 1][j] >= ans[i][j - 1]){ i--; } else { j--; } } return new String(end); } public static void main(String[] args){ System.out.println(longestPalindrome("abcbabbba")); } }
class Solution { public: /** * * @param s string字符串 * @return string字符串 */ string longestPalindrome(string s) { // write code here int n=s.size(); int len=0; int pos; vector<vector<bool> > p(n,vector<bool>(n,false)); for(int i=0;i<n;i++) { for(int j=i;j>=0;j--) { if((s[i]==s[j])&&(i-j<2||p[i-1][j+1])) { p[i][j]=true; if(i-j+1>=len) { len=i-j+1; pos=j; } } } } string res=s.substr(pos,len); return res; } };
class Solution { public: /** * * @param s string字符串 * @return string字符串 */ bool Is_Prime(string str){//判断字符串str是否回文 for(int i=0;i<str.length()/2;i++){ if(str[i]!=str[str.length()-1-i]){ return false; } } return true; } string longestPalindrome(string s) { // write code here string ans=s.substr(0,1),str; for(int i=0;i<s.length();i++){//从字符串首字母遍历 str=s[i]; for(int j=i+1;j<s.length();j++){//依次往后加 str=str+s[j]; if(Is_Prime(str)&&str.length()>ans.length()){//储存最长的回文 ans=str; } } } return ans; } };
class Solution: def longestPalindrome(self , s ): # write code here l,r=0,0 maxstr='' flag=0 while(r!=len(s)): temstr='' temstr=s[l:r] if s[l:r]!=temstr[::-1] and flag==0: r+=1 elif s[l:r]==temstr[::-1] and len(s[l:r])>=2 and flag==0: if len(maxstr)<len(s[l:r]): maxstr=s[l:r] flag=1 r+=1 elif s[l:r]==temstr[::-1] and flag==1: if len(maxstr)<len(s[l:r]): maxstr=s[l:r] r+=1 elif s[l:r]!=temstr[::-1] and flag==1: l+=1 if len(maxstr)<len(s[l:r]): maxstr=s[l:r] else: r+=1 temstr=s[l:r] if s[l:r]==temstr[::-1]: if len(maxstr) < len(s[l:r]): maxstr = s[l:r] elif s[l:r]!=temstr[::-1]: while(l<r and s[l:r]!=temstr[::-1]): l+=1 temstr=s[l:r] if s[l:r]==temstr[::-1]: if len(maxstr) < len(s[l:r]): maxstr = s[l:r] return maxstr
#python实现 class Solution: def longestPalindrome(self , s )-> str: # write code here res = '' for i in range(len(s)): start = max(0,i-len(res)-1) temp = s[start:i+1] if temp == temp[::-1]: res = temp else: temp = temp[1:] if temp == temp[::-1]: res = temp return res