对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。
给定字符串A以及它的长度n,请返回最长回文子串的长度。
public int getLongestPalindrome(String A, int n) { // 第 i 个字符到第 j 个字符是否是回文串 boolean[][] dp = new boolean[n][n]; int max = 0; // 字符串首尾字母长度差 (d = j-i) for (int d = 0; d < n; d++) { // 字符串起始位置 i for (int i = 0; i < n-d; i++) { // 字符串结束位置 j int j = i+d; // 如果字符串 i 到 j 的首尾相等,再根据字符串 i-1 到 j-1 来确定,即得到递推公式 if(A.charAt(i) == A.charAt(j)) { if(d == 0 || d == 1) { dp[i][j] = true; } else { dp[i][j] = dp[i+1][j-1]; } if(dp[i][j]) { // 更新最大长度 max = Math.max(max, d+1); } } } } return max; }
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here int[][] dp = new int[n][n]; int max = 1; for (int i = 0; i < n; ++i) { dp[i][i] = 1; } char[] a = A.toCharArray(); for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; if (len == 2 && a[i] == a[j]) { dp[i][j] = len; max = 2; continue; } if (a[i] == a[j] && dp[i + 1][j - 1] != 0) { dp[i][j] = len; max = len; } } } return max; } }
class Solution:
def getLongestPalindrome(self, A, n):
maxLen=1
if A==A[::-1]:return n
for i in range(n):
if i-maxLen>=1 and A[i-maxLen-1:i+1]==A[i-maxLen-1:i+1][::-1]:
maxLen+=2
continue
if i-maxLen>=0 and A[i-maxLen:i+1]==A[i-maxLen:i+1][::-1]:
maxLen+=1
return maxLen
import java.util.*; public class Solution { //判断回文的函数 public boolean isHuiWen(String A, int n){ int k = n / 2; for (int i = 0; i < k; ++i) { if (A.charAt(i) != A.charAt(n-1-i)) return false; } return true; } public int getLongestPalindrome(String A, int n) { int maxlen=0; for(int i=0 ;i< n ;i++){ for(int j=i+1 ;j<=n ;j++){ //两层循环遍历出所有的子串,并且逐一判断是否是回文 if(isHuiWen(A.substring(i, j),j-i)){ if(j-i>maxlen) maxlen=j-i; } } } return maxlen; } }
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; } };
//直接暴力,适用于求长度以及具体回文串 class Solution { public: int getLongestPalindrome(string A, int n) { // write code here int start,maxlength=0; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) { int tmp1,tmp2; for(tmp1=i,tmp2=j;tmp1<tmp2;tmp1++,tmp2--) { if(A[tmp1]!=A[tmp2]) break; } if(tmp1>=tmp2&&j-i>=maxlength) { maxlength=j-i+1; start=i; } } return maxlength; } };
import java.util.*; import java.lang.*; public class Solution { //求a和b的最长公共子字符串长度 public int lcs(String a, String b) { int max_len = 0; int[][]dp = new int[a.length() + 1][b.length() + 1]; for (int i = 1; i <= a.length(); i++) { for (int j = 1; j <= b.length(); j++) { if (a.charAt(i - 1) == b.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > max_len) max_len = dp[i][j]; } } } return max_len; } public int getLongestPalindrome(String A, int n) { // write code here String B = new StringBuilder(A).reverse().toString(); return lcs(A, B); } }
寻找字符串中最长的回文串
改进版动态规划,时间复杂度O(n*n),空间复杂度O(n)
从字符串后面开始探索
whetherSolution[j]为1表示A[i,j+1]为回文串
循环过程中,在whetherSolution里面比当前j小的whetherSolution的标记都为上一个i的
(除了i,因为A[i,i+1]单个字符为回文串)
如果得到一个回文串,和过程中保存的最长回文串比较长度。
这个等号是为了取到长度相等时排在前面的回文串。如果去掉是取到排在后面的
def getLongestPalindrome(self, A, n): if n <= 1: return n whetherSolution = [0 for i in range(n)] theSolutionMax = 1 whetherSolution[-1] = 1 for i in range(n - 2, -1, -1): whetherSolution[i] = 1 for j in range(n - 1, i, -1): if whetherSolution[j - 1] and A[i] == A[j]: whetherSolution[j] = 1 if theSolutionMax < j - i + 1: theSolutionMax = j - i + 1 else: whetherSolution[j] = 0 return theSolutionMax
public class Solution { public int getLongestPalindrome(String A, int n) { int[][] dp = new int[n][n]; int max = 1; for (int i = 0; i < n; ++i) { dp[i][i] = 1; } char[] a = A.toCharArray(); for(int i=n-2;i>=0;i--){ for(int j=i;j<n;j++){ if(j>0&&dp[i+1][j-1]!=0&&a[i]==a[j]||j>0&&i==j-1&&a[i]==a[j]) dp[i][j] = 2+dp[i+1][j-1]; if(dp[i][j]>max) max=dp[i][j]; } } return max; } }
# -*- coding:utf-8 -*- class Solution: def getLongestPalindrome(self, A, n): # write code here A='#'+'#'.join(A)+'#' n=len(A) RL=[0]*n MaxRight=0 pos=0 MaxLen=0 for i in range(n): if i<MaxRight: RL[i]=min(RL[2*pos-i], MaxRight-i) else: RL[i]=1 while i-RL[i]>=0 and i+RL[i]<n and A[i-RL[i]]==A[i+RL[i]]: RL[i]+=1 if RL[i]+i-1>MaxRight: MaxRight=RL[i]+i-1 pos=i MaxLen=max(MaxLen, RL[i]) return MaxLen-1 # -*- coding:utf-8 -*- class Solution: def getLongestPalindrome(self, A, n): # write code here A='#'+'#'.join(A)+'#' n=len(A) RL=[0]*n MaxRight=0 pos=0 MaxLen=0 for i in range(n): if i<MaxRight: RL[i]=min(RL[2*pos-i], MaxRight-i) else: RL[i]=1 while i-RL[i]>=0 and i+RL[i]<n and A[i-RL[i]]==A[i+RL[i]]: RL[i]+=1 if RL[i]+i-1>MaxRight: MaxRight=RL[i]+i-1 pos=i MaxLen=max(MaxLen, RL[i]) return MaxLen-1 #搬的,参考了网上的manacher算法的文章
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here int res = 0; for (int i = 0;i < A.length();i++) { res = Math.max(spread(A, i, i), res); } for (int j = 0;j < A.length()-1;j++) { if (A.charAt(j) == A.charAt(j+1)) { res = Math.max(spread(A, j, j+1), res); } } return res; } public int spread(String A, int start, int end) { while (start >= 0 && end < A.length() && A.charAt(start) == A.charAt(end)) { start--; end++; } return end-start-1; } }
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: bool isSolution(string A, int l, int r){ while(l < r){ if(A[l++] != A[r--]) return false; } return true; } int getLongestPalindrome(string A, int n) { // write code here int res = 0; for(int i = 0; i < n-1; i++){ for(int j = i+1; j < n; j++){ if(isSolution(A, i, j) && j-i+1 > res) res = j-i+1; } } return res; } };
class Solution { public: int getLongestPalindrome(string A, int n) { // write code here int res = 0; for(int i = 0; i < n; i++){ int tmp1 = 1; int tmp2 = 2; int l, r; l = i-1; r = i+1; while(l >= 0 && r < n && A[l] == A[r]){ tmp1 += 2; l--; r++; } l = i-1; r = i+2; while(l >= 0 && r < n && A[l] == A[r]){ tmp2 += 2; l--; r++; } res = max(res, tmp1); if(A[i] == A[i+1]) res = max(res, tmp2); } 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; } };
//详情请点击博客链接(链接在最下方) import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here int count=0; //记录每次字符串的长度 int max=0; //记录最大字符串的长度 for(int i=0;i<n;i++){ for(int j=i+1;j<=n;j++){ String s=A.substring(i,j);//通过for截取出所有可能出现的字符串 if(isPalindromic(s)){//进行判断:2步骤 count=s.length(); if(max<count){ //进行判断:3步骤 max=count; } } } } return max; } public static boolean isPalindromic(String s) { int i = 0; int j = s.length() - 1; while (i <= j) { //取出新得到的字符串挨个字符进行比较 if (s.charAt(i) != s.charAt(j)) { return false; } i++; j--; } return true; } } ———————————————— 版权声明:本文为CSDN博主「峰回路转」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/qq_44840148/article/details/105123450
class Solution { public: int getLongestPalindrome(string str, int n) { int max=0; string newstr; for(char c:str){ newstr+="#"; newstr+=c; } newstr+="#"; for(int i=0;i<2*n+1;i++){ for(int len=0;;len++){ if(newstr[i-len]!=newstr[i+len]||i-len<0||i+len>=2*n+1){ break; } if(max<len*2+1){ max=len*2+1; } } } return max/2; } };没用动态规划,从中心找回文,避免考虑奇偶就在每个字符中间及首位加了#使回文串必为奇数,返回的长度除以2就行了,时间复杂度大概O(n^2),主要容易理解
//仅作记录,方便日后查阅 class Solution { public: int getLongestPalindrome(string A, int n) { // write code here vector<vector<bool> >dp(n,vector<bool>(n,false));//dp[i][j]记录A[i]与A[j]是否相同 for(int i=0; i<n; i++) dp[i][i]=true;//自身显然相等 int ans=1;//最短长度为1 for(int i=n-1; i>=0; i--)//从倒数第二个字符开始比较 { for(int j=i+1; j<n; j++)//j从i+1开始 { if(A[i]==A[j]) { if(j==i+1) dp[i][j]=true;//相邻的字符相等即为true else if(dp[i+1][j-1])//不相邻的字符,查看内侧是否相同 dp[i][j]=true; if(dp[i][j]&&ans<j-i+1) ans=j-i+1; } } } return ans; } };
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here String str=A; int len=str.length(); int[][] dp=new int[len][len]; int ans=1; for(int i=0;i<len;i++){ dp[i][i]=1; if(i<len-1){ if(str.charAt(i)==str.charAt(i+1)){ dp[i][i+1]=1; ans=2; } } } for(int L=3;L<=len;L++){ for(int i=0;i+L-1<len;i++){ int j=i+L-1; if(str.charAt(i)==str.charAt(j) && dp[i+1][j-1]==1){ dp[i][j]=1; ans=L; } } } return ans; } }