对于长度为n的一个字符串A(仅包含数字,大小写英文字母),请设计一个高效算法,计算其中最长回文子串的长度。
数据范围:
要求:空间复杂度 ,时间复杂度
进阶: 空间复杂度 ,时间复杂度
class Solution { public: bool pan(string a,int start,int end){ //判断是否回文 bool flag=true; while(start<=end){ if(a[start]!=a[end]){ flag=false; break; } start++; end--; } return flag; } int getLongestPalindrome(string A, int n) { int max=-1; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if(A[i]==A[j]&&pan(A,i,j)&&j-i+1>max){ max=j-i+1; } } } return max; } };
int getLongestPalindrome(string A) { // write code here vector<vector<int> >dp(A.size(), vector<int>(A.size())); int ret = 1; for(int i = 0; i < A.size(); ++i) { dp[i][i] = 1; if(i < A.size() - 1) { if(A[i] == A[i+1]) { dp[i][i+1] = 1; ret = 2; } } } for(int L = 3; L <= A.size() ;++L) for(int i = 0; i + L - 1 < A.size(); ++i) { int j = i + L - 1; if(A[i] == A[j] && dp[i + 1][j - 1]) { dp[i][j] = 1; ret = L; } } return ret; }都会背了...
manacher算法
时间复杂度:O(n) 空间复杂度:O(n)
参考文献:Manacher算法的详细讲解
class Solution: def manacher(self, s, n, dp): ms = '' ms += '$#' for i in range(n): ms += s[i] ms += '#' index = 0 maxpos = 0 for i in range(len(ms)): if i < maxpos: dp[i] = min(dp[2*index-i], maxpos-i) else: dp[i] = 1 while i - dp[i] > 0 and i + dp[i] < len(ms) and ms[i-dp[i]] == ms[i+dp[i]]: dp[i] += 1 if i + dp[i] > maxpos: maxpos = i + dp[i] index = i def getLongestPalindrome(self , A: str) -> int: n = len(A) dp = [0 for i in range(n*2 + 2)] self.manacher(A, n, dp) res = 0 for i in range(n*2+2): res = max(res, dp[i]-1) return res
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param A string字符串 # @return int整型 # class Solution: def fun(self, s, left, right): while left >=0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return right - left - 1 # Manacher算法, 感觉有点想剪枝的策略 def Manacher(self, s): S = '#'.join(list(s)) S = '@#' + S + '#' P = [0 for _ in range(len(S)+10)] idx, mx, max_num, max_id= 0,0,0,0 for i in range(1, len(S)): # 如果当前的i在最大回文半径内,则进行选择当前最大半径下标到当前下标的距离 和 对称位置2*idx - 1的最大半径 最小值 # 然后进行从对应的半径P[i]进行开始向左和右进行搜索 P[i] = min(P[2 * idx - i], mx - i) if mx > i else 1 while i - P[i] >=0 and i + P[i] < len(S) and S[i + P[i]] == S[i - P[i]]: P[i] += 1 # 如果当前的最大半径index大于当前的mx,则进行替换 # 更新最大回文半径中心id if i + P[i] > mx: mx = i + P[i] idx = i if P[i] > max_num: max_num = P[i] max_id = idx return max_num - 1 def getLongestPalindrome(self , A: str) -> int: # write code here # 最长回文子串 O(n^2) # 从左到右进行遍历字符串,然后计算1、中心字符扩散;2、两个字符扩散 # rel = 1 # for i in range(len(A) - 1): # rel = max(rel, max(self.fun(A, i, i), self.fun(A, i, i+1))) return self.Manacher(A)
TIPS:对于O(n^2)的做法:
1、通过将字符串进行反转,然后使用动态规划计算和原始字符串的最长共同子串;
2、通过中心扩散的做法, 遍历一遍字符串,对于每个字符进行向两边扩散计算回文子串的最大长度;
对于时间复杂度O(n)的做法:
Manacher算法:
1、首先将字符串‘123456’,处理成‘@#1#2#3#4#5#6#’的形式;
2、然后设定一个备忘录dp[i],记录节点i的最大回文子串半径大小,设定额外两个变量idx,max_b,分别表示遍历过程中,当前字符前最大回文子串的中心下标以及最大回文子串的右界;
3、从头开始遍历,如果最大有界大于当前所遍历的字符下标,则取min(右界到当前下标的距离,当前下标在当下最大回文子串中心对称字符的最大半径P[2 *idx - cur_index]]),否则直接设定为1,
4、对当前字符可能的最大半径之后,进而从半径大小开始向两端遍历
5、如果更新后的当前字符的最大半径【右界】大于当前的右界,则进行更新右界和最大回文字符中心index
6、更新结果max_num【最终的max_num - 1则是最长回文子串的长度】
public int getLongestPalindrome(String A, int n) { //一个字符肯定为1 if(A.length()==1) return 1; //两个字符并且相同肯定为2 if(A.length()==2&&A.charAt(0)==A.charAt(1)) return 2; //两个字符并且不相同相同肯定为1 if(A.length()==2&&A.charAt(0)!=A.charAt(1)) return 1; int maxLen = 0; for(int i=0; i<A.length(); i++){ ArrayList<Integer> list = new ArrayList<Integer>(); char tmp = A.charAt(i); //双层遍历,0-A.length() 1-A.length....... for(int j=i+1; j<A.length(); j++){ if(A.charAt(j) == tmp){ list.add(j); } } //遍历list for(int k=0; k<list.size(); k++){ //因为substring()含头不含尾所以+1 Boolean flag = check(A.substring(i, list.get(k)+1)); //成功就截取长度 if(flag){ maxLen = Math.max(maxLen,list.get(k)-i+1); } } } return maxLen; } public boolean check(String s){ for (int i = 0; i < s.length(); i++) { if(s.charAt(i)!=s.charAt(s.length()-1-i)){ return false; } } return true; }
方法1:中心扩展法
public class Solution { // 方法1:遍历,时间复杂度为 O(n^2) public int getLongestPalindrome(String A, int n) { int maxLen = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { // 这里一定要注意奇数长度和偶数长度的回文串都要考虑 maxLen=Math.max(maxLen,getMaxHui(i-1,i+1,A)); maxLen=Math.max(maxLen,getMaxHui(i,i+1,A)); } return maxLen; } // 获取指定 l r 开始的最长的回文串长度 private int getMaxHui(int l,int r,String A) { while (l>=0 && r<=A.length()-1 && A.charAt(l)==A.charAt(r)) { l--; r++; } return r-l-1; } }
方法2:动态规划
public class Solution { public int getLongestPalindrome(String A) { if (A.length()<=1) return A.length(); int n = A.length(); int[][] dp = new int[n][n]; int res = 1; int len = A.length(); // 长度为 1 的串,肯定是回文的 for (int i = 0; i < n; i++) { dp[i][i]=1; } // 将长度为 2-str.length 的所有串遍历一遍 for (int step = 2; step <= A.length(); step++) { for (int l = 0; l < A.length(); l++) { int r=l+step-1; if (r>=len) break; if (A.charAt(l)==A.charAt(r)) { if (r-l==1) dp[l][r]=2; else dp[l][r]=dp[l+1][r-1]==0?0:dp[l+1][r-1]+2; } res=Math.max(res,dp[l][r]); } } return res; } }
public int getLongestPalindrome(String A, int n) { if(n == 0) return 0; if(n == 1) return 1; int maxLen = 1; for(int i = 0; i<n; i++){ for(int j = 1; i-j>=0 && i+j<n; j++){ if(A.charAt(i-j) == A.charAt(i+j)){ int len = 2*j+1; maxLen = Math.max(len,maxLen); } if(A.charAt(i-j) != A.charAt(i+j))break; } for(int k = 1; i-k+1>=0 && i+k<n; k++){ if(A.charAt(i-k+1) == A.charAt(i+k) ) { int len = 2*k; maxLen = Math.max(len,maxLen); } if(A.charAt(i-k+1) != A.charAt(i+k)) break; } } return maxLen; }
#马拉车中心扩散 class Solution: def getLongestPalindrome(self, A, n): strin = [] A = list(A) A.reverse() for i in range(2*n+1): if i % 2 == 0: strin.append('*') else: strin.append(A.pop()) maxr = 0 for index,item in enumerate(strin): step = 1 try: while strin[index-step] == strin[index+step]: step+=1 except: rest = step - 1 if rest > maxr: maxr = rest continue rest = step - 1 if rest > maxr: maxr = rest return maxr
class Solution { public: int getLongestPalindrome(string A, int n) { // write code here int Max = 0,i = 0,j = 0,k = 0,tmp = 0; for(i = 0; i < n;i++) { if(A[i] != A[i + 1] && A[i] != A[i + 2]) { continue; }else{ if(A[i] == A[i + 1]) { if(A[i] != A[i + 2]) { tmp = 2; k = i+2; }else{ if(A[i - 1] == A[i + 2]) { tmp = 2; k = i+2; }else{ tmp = 3; k = i + 3; } } }else if(A[i] == A[i + 2]) { tmp = 3; k = i + 3; } for(j = i-1;j >= 0 && k <= n;j--,k++) { if(A[j] == A[k]) { tmp += 2; }else{ break; } } if(Max < tmp) Max = tmp; } } return Max; } };
时间复杂度:o(n) import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here char[] chars = A.toCharArray(); int max = 1; int left,right; for(int i = 0 ; i < n;i++){ int res1 = process(chars,i-1,i+1,n,1); int res2 = process(chars,i,i+1,n,0); int count = Math.max(res1,res2); max = Math.max(count,max); } return max; } public int process(char[] chars , int left,int right,int n,int count){ while(left>=0 && right<n){ if(chars[left] != chars[right]){ break; } count+=2; left--; right++; } return count; } }
//动态规划 int getLongestPalindrome(string A, int n) { // write code here int res=1; vector<vector<bool>> dp(n,vector<bool>(n,false)); //dp[i][j]:从i到j的字符子串是不是回文串 for(int i=0; i<n; i++) { dp[i][i]=true; } for(int j=1; j<n; j++) { for(int i=0; i<j; i++) { if(A[i]!=A[j]) dp[i][j]=false; else { if(j-i+1<=3) //如果长度小于等于3,直接就是回文串 dp[i][j]=true; else //长度大于等于4 dp[i][j]=dp[i+1][j-1]; } if(dp[i][j] && j-i+1>res) //更新最大长度 res = j-i+1; } } return res; //中心扩散 int sublen(string& A, int l, int r) { while(l>=0 && r<A.size() && A[l]==A[r]) { l--; r++; } return r-l-1; } int getLongestPalindrome(string A, int n) { int res=1; for(int i=0; i<n; i++) { int r1 = sublen(A, i, i); int r2 = sublen(A, i, i+1); res = res>r1?res:r1; res = res>r2?res:r2; } return res; }
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here if(n<2){ return n; } int maxLength=1; int begin=0; char[] chararray=A.toCharArray(); for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ if(j-i+1>maxLength && validPalindrome(chararray,i,j)){ maxLength=j-i+1; begin=i; } } } return maxLength; } public boolean validPalindrome(char[] chararray,int left,int right){ while(left<right){ if(chararray[left]!=chararray[right]){ return false; } left++; right--; } return true; } }
import java.util.*; //喜极而泣啊!写代码五分钟,调bug2小时 //说下思路: public class Solution{ public int getLongestPalindrome(String A, int n) { char [] strArr = A.toCharArray(); int length=0; // l为左,r为右,当l到r范围的字符串为回文,(两端相等,并依次递归,直到所有相等,则为回文) for (int l=0; l < n; l++) { for (int r = l; r < n; r++) { //设置一个flag,当回文时为1,不回文为-1 int flag=0,r1=r,l1=l; while(l1<=r1) { if(strArr[l1]==strArr[r1]) flag=1; else {flag=-1;break;} l1++; r1--; } if(flag==1)length=Math.max(length,r-l+1); } } return length; } }
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here int [][] dp = new int [n+1][n+1]; int res = 1; for(int i = 0;i < n;++i) dp[i][i] = 1; for(int i = 0,j = i+1;i < n && j < n;++i,++j){ if(A.charAt(i) == A.charAt(j)){ dp[i][j] = 2; res = 2; } else dp[i][j] = 0; } int dis = 2; while(dis < n){ for(int i = 0,j = i+dis;j < n;++i,++j){ if(A.charAt(i) == A.charAt(j) && dp[i+1][j-1] != 0){ dp[i][j] = 2+dp[i+1][j-1]; res = Math.max(dp[i][j],res); }else dp[i][j] = 0; } ++dis; } return res; } }
export function getLongestPalindrome(A: string, n: number): number { // write code here if(!n) return 0 let res = 1 const dp = [] for(let i = n -1;i>=0;i--){ dp[i] = [] for(let j = i;j<n;j++){ if(j - i == 0) dp[i][j] = true else if(A[i] == A[j]&&j-i == 1) dp[i][j] = true else if(A[i] == A[j] && dp[i+1][j-1]) dp[i][j] = true if( dp[i][j]&& j - i + 1 >res) res = j - i + 1 } } return res }
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { int maxCount = 0; for (int i = 1; i < A.length() ; i++){ int left = i -1; int right = i +1; int count = 1; maxCount = getMaxCount(A, maxCount, left, right, count); left = i -1; right = i; count = 0; maxCount = getMaxCount(A, maxCount, left, right, count); } // write code here return maxCount; } private int getMaxCount(String A, int maxCount, int left, int right, int count) { while (left>= 0 && right <= A.length()-1 && A.charAt(left) == A.charAt(right)){ left--; right++; count+=2; } maxCount = Math.max(count,maxCount); return maxCount; } }
class Solution { public: int getLongestPalindrome(string s, int n) { int res=0;int l,r; for(int i=0;i<n;i++) { l=i-1; r=i+1; while(l>=0&&r<=n-1&&s[l]==s[r]) { res=max(res,r-l+1); l--;r++; } l=i;r=i+1; while(l>=0&&r<=n-1&&s[l]==s[r]) { res=max(res,r-l+1); l--;r++; } } return res; } };//借鉴某位大神的写法写了一遍
class Solution { public: int getLongestPalindrome(string A, int n) { if (n < 2) return n; int max = 1; for (int i = 0; i < n; i++) { for (int j = 1; i-j >= 0 && i+j < n; j++) { if (A[i-j] == A[i+j]) { int t = j*2 + 1; max = t > max ? t : max; } else break; } for (int j = 0; i-j-1 >= 0 && i+j <n; j++) { if (A[i-j-1] == A[i+j]) { int t = j*2 + 2; max = t > max ? t : max; } else break; } } return max; } };