贵州省铁路建设办公室网站,如何查名下是否有注册的公司,网站模板开发主要作用,做网站一定要效果图吗题目要求 解题思路
这一类型#xff08;回文子串#xff09;主要有两种解决方法#xff0c;一种是动态规划#xff0c;另一种是中心拓展算法。 动态规划#xff1a; 本质问题就是在i-j区间是不是回文的。这样的话我们在 i 和 j 位置的值相等时#xff0c;判断如下三种情…题目要求 解题思路
这一类型回文子串主要有两种解决方法一种是动态规划另一种是中心拓展算法。 动态规划 本质问题就是在i-j区间是不是回文的。这样的话我们在 i 和 j 位置的值相等时判断如下三种情况即可 1. i j 时肯定是回文的 2. i 1 j 时也肯定是回文的 3. i 1 j 时那就需要判断 i 1 到 j - 1 位置是否是回文的即可 中心拓展算法 本质就是利用字串的特性进行暴力枚举我们分别枚举每一个位置的值分别判断奇数个数据和偶数个数据时情况即可。
解题代码
class Solution
{
public:string longestPalindrome(string s) {//动态规划//1.创建dp表//2.初始化//3.填表//4.返回值int ns.size();vectorvectorbool dp(n,vectorbool(n));int len1,begin0;//填表顺序从下往上for(int in-1;i0;i--){for(int ji;jn;j){if(s[i]s[j])dp[i][j]i1j?dp[i1][j-1]:true;//处理返回值if(dp[i][j]j1-ilen){lenj1-i;begini;}}}return s.substr(begin,len);}
};class Solution
{
public:string longestPalindrome(string s) {int ns.size(),len1,begin0;//中心扩展for(int i0;in;i){//奇数int lefti,righti;while(left0rightns[left]s[right]){left--;right;}if(right-left-1len){beginleft1;lenright-left-1;}//偶数lefti,righti1;while(left0rightns[left]s[right]){left--;right;}if(right-left-1len){beginleft1;lenright-left-1;}}return s.substr(begin,len);}
};
