这道题我主要是通过动态规划来进行解题,看了我好久(解析),生疏了呀。
首先就是判断一个字符串是不是回文,我们可以设置两个指针,从前往后进行判断即可,运用暴力解题法,这里运用的动态规划法主要是要搞清楚原理即可。
中心思想就是先判断两端的是否相等,若是则 dp[i][j] = true,然后是从短到长的一个过程,与此同时不断更新最长子串的下标,最后再返回,代码里面有详细的解释。
class Solution {
public:string longestPalindrome(string s) {// 1.动态规划(很有意思)int n=s.size();if(n<2) return s; //长度为1时直接返回即可// maxLen和begin的作用在于存满足条件的字符串的上限和下限,用于最后结果的截取int maxLen=1,begin=0;// dp[i][j] 表示 s[i..j] 是否是回文串vector<vector<int>> dp(n,vector<int>(n));for(int i=0;i<n;i++) dp[i][i]=true;// L表示子串长度for(int L=2;L<=n;L++){// i表示能确定左边界for(int i=0; i<n;i++){//j为右边界int j=i+L-1;if(j>=n) break; // 越界 跳//左右边界值相等且在长度if(s[i] != s[j]){dp[i][j]=false;}else{//当满足条件的子串的长度小于等于3时,此时的j-i是<=2的,所以可以以此来进行判断if(j-i<3 ){dp[i][j]=true;}else{dp[i][j]=dp[i+1][j-1];}}//最后进行判断,并更新下标的值最后进行返回即可if(dp[i][j]&&j-i+1>maxLen){maxLen=j-i+1;begin=i;}}}return s.substr(begin,maxLen);}
};
龙年快乐哦~