一、回文子串
该题有3种解法
(1)中心扩展算法(在字符串章节有介绍)时间复杂度O(N^2),空间复杂度O(1)
(2)马丁车算法(专门用来解决回文串问题,但是适用返回太窄)时间复杂度O(N),空间复杂度O(N)
(3)动态规划(可以将所有回文信息都保存在dp表中)时间复杂度O(N^2),空间复杂度O(N^2)
这边重点介绍动态规划的做法。
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示s字符串[i,j]的子串是否是回文串(i<=j)只需处理右上区即可
2、状态转移方程
dp[i][j]:
(1)s[i]!=s[j]——>false
(2)s[i]==s[j]——>
i==j true
i+1==j true
dp[i+1][j-1]
3、初始化
无需初始化
4、填表顺序
dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要
5、返回值
dp表中true的个数
class Solution {
public:
int countSubstrings(string s) {
//动态规划的做法
int ret=0;
//s[i]==s[j] 1、i==j 2、i+1==j 3、dp[i+1][j-1]?
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
//只要右上半区
for(int i=n-1;i>=0;--i) //要从下往上 左右无所谓,因为用不到
for(int j=i;j<n;++j) //只要右上半区
if(s[i]==s[j]) ret+=dp[i][j]=i+1<j?dp[i+1][j-1]:true;
return ret;
}
};
二、最长回文子串
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示s字符串[i,j]的子串是否是回文串(i<=j)只需处理右上区即可
2、状态转移方程
dp[i][j]:
(1)s[i]!=s[j]——>false
(2)s[i]==s[j]——>
i==j true
i+1==j true
dp[i+1][j-1]
3、初始化
无需初始化
4、填表顺序
dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要
5、返回值
dp表中为true以及长度最大的子串的起始位置和长度
class Solution {
public:
string longestPalindrome(string s) {
//动态规划的思想
int begin=0,len=1;//帮助我们返回结果
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
for(int i=n-1;i>=0;--i)
for(int j=i;j<n;++j) //右上角部分
{
if(s[i]==s[j])
{
dp[i][j]=i+1<j?dp[i+1][j-1]:true;
if(dp[i][j]&&len<j-i+1)
{
begin=i;
len=j-i+1;
}
}
}
return s.substr(begin,len);
}
};
三、分割回文子串I
解法1:动归预处理+回溯
class Solution {
public:
//动归预处理+回溯
vector<vector<bool>> dp;//dp预处理
vector<vector<string>> ret;//记录返回的结果
vector<string> path;//记录路径的结果
int n;
vector<vector<string>> partition(string s) {
//dp预处理
n=s.size();
dp.resize(n,vector<bool>(n));
for(int i=n-1;i>=0;--i)
for(int j=i;j<n;++j)
if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
//将dp数组交给dfs去处理
dfs(s,0);
return ret;
}
void dfs(string&s,int i)
{
if(i==n)
{
ret.push_back(path);
return;
}
for(int j=i;j<n;++j)
if(dp[i][j])
{
path.emplace_back(s.substr(i,j-i+1));
dfs(s,j+1);
path.pop_back();
}
}
};
解法2:回溯+记忆化搜索
class Solution {
public:
//回溯+记忆化搜索
vector<vector<int>> f;//记忆化数组 0表示未搜索,1表示回文,-1表示不回文
vector<vector<string>> ret;//记录返回的结果
vector<string> path;//记录路径的结果
int n;
vector<vector<string>> partition(string s) {
n=s.size();
f.resize(n,vector<int>(n));
//交给dfs帮助我们解决
dfs(s,0);
return ret;
}
void dfs(const string&s,int i)
{
if(i==n)
{
ret.emplace_back(path);
return;
}
for(int j=i;j<n;++j)
if(ispal(s,i,j))
{
path.emplace_back(s.substr(i,j-i+1));
dfs(s,j+1);
path.pop_back();
}
}
bool ispal(const string&s,int i,int j) //判断i->j是否回文
{
//先看看备忘录
if(f[i][j]) return f[i][j];
if(s[i]!=s[j]) return f[i][j]=false;
else return f[i][j]=i+1<j?ispal(s,i+1,j-1):true;
}
};
四、分割回文子串II
算法原理:
1、状态表示(经验+题目要求)
dp[i]表示s字符串[0,i]区间上的最长子串的最小分割次数
2、状态转移方程
dp[i]:
(1)0-i回文——>0
(2)0-i不是回文——>j-i是否回文——>min(dp[i],dp[j-1]+1)
3、初始化
都初始化为整型最大值,否则最后dp表里都是0会影响结果
4、填表顺序
dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要
5、返回值
dp[n-1]
class Solution {
public:
int minCut(string s)
{
int n=s.size();
vector<vector<bool>> ispal(n,vector<bool>(n));
for(int i=n-1;i>=0;--i)
for(int j=i;j<n;++j) //右上角部分
if(s[i]==s[j]) ispal[i][j]=i+1<j?ispal[i+1][j-1]:true;
//第二次枚举 尝试去分割
vector<int> dp(n,INT_MAX);//初始化为无穷大
for(int i=0;i<n;++i)
//先看看左边的部分
if(ispal[0][i]) dp[i]=0;
else
for(int j=1;j<=i;++j)//去看看左边 要怎么切割 左开右闭
if(ispal[j][i]) dp[i]=min(dp[i],dp[j-1]+1);//j代表最后一个回文串的起始位置
return dp[n-1];
}
};
五、分割回文子串III(经典)
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示对于字符串的前i个字符,将他分割成j个子串,所需修改的最少字符数
2、状态转移方程
int cost(string&s,int l,int r) 表示从s的i-j位置,变成回文串所需要的最小修改次数
dp[i][j]:
(1)j==1(没有分割) cost(s,0,i-1)
(2)j>1——>min(dp[i][j],dp[m][j-1]+cost(s,m,i-1))
3、初始化
初始化成INT_MAX 确保不影响最终结果 dp[0][0]=0 确保不影响结果
4、填表顺序
上到下,左到右
5、返回值
dp[n][k]
class Solution {
public:
int palindromePartition(string s, int k) {
//dp[i][j]表示对于字符串的前i个字符,将他分割成j个子串,所需修改的最少字符数
int n=s.size();
vector<vector<int>> dp(n+1,vector<int>(k+1,INT_MAX));
dp[0][0]=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=min(k,i);++j)
if(j==1) dp[i][j]=cost(s,0,i-1);
else
for(int m=j-1;m<i;++m) dp[i][j]=min(dp[i][j],dp[m][j-1]+cost(s,m,i-1));
//找前面的状态 0->i 分成j个
//dp0->m+ cost m->i
return dp[n][k];//0->n k
}
int cost(string&s,int l,int r)
{
int ret=0;
for(int i=l,j=r;i<j;++i,--j)
if(s[i]!=s[j]) ++ret;//需要修改一个才能成为回文
return ret;
}
};
六、分割回文串IV
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示s字符串[i,j]的子串是否是回文串(i<=j)只需处理右上区即可
2、状态转移方程
dp[i][j]:
(1)s[i]!=s[j]——>false
(2)s[i]==s[j]——>
i==j true
i+1==j true
dp[i+1][j-1]
3、初始化
无需初始化
4、填表顺序
dp[i][j]会用到dp[i+1][j-1],所以必须要从下往上填 , 左右顺序不重要
5、返回值
第二次枚举,先固定第一个位置,然后固定第二个位置,看看由两个位置分割出来的三个区域是否都为true
class Solution {
public:
bool checkPartitioning(string s) {
//将结果存到dp表中
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n));
for(int i=n-1;i>=0;--i)
for(int j=i;j<n;++j) //右上角部分
if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;
//第二次枚举 先固定第一个,然后固定第二个,然后看看3个是不是都是true即可
for(int i=1;i<n-1;++i)
for(int j=i;j<n-1;++j)
if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;
return false;
}
};
七、不重叠回文子字符串的最大数目
class Solution {
public:
int maxPalindromes(string s, int k) {
//dp[i]表示0->i中的不重叠回文子字符串的最大数目
int n=s.size();
vector<int> dp(n+1);
//如果s[i]不在回文串中 dp[i+1]=dp[i]
//如果s[r]在回文串中,采用中心扩展,l->r是回文子串,且r-l+1>=k 有dp[i]=max(dp[i],dp[l-1]+1)
for(int i=0;i<n*2-1;++i)
{
//两边到中间不适合判断长度,应该从中间到两边
int l=i/2,r=l+i%2; //中心扩展判断是否回文
dp[l+1]=max(dp[l],dp[l+1]);
for(;l>=0&&r<n&&s[l]==s[r];--l,++r)
if(r-l+1>=k)
{
dp[r+1]=max(dp[r+1],dp[l]+1);
break;
}
}
return dp[n];
}
};
八、最长回文子序列
class Solution {
public:
int longestPalindromeSubseq(string s)
{
//子序列和子串的区别就是可以不连续
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n));//只会用到右上半部分
for(int i=n-1;i>=0;--i)
{
//dp[i][j]表示i-j区间内所有子序列中,最长回文子序列的长度
dp[i][i]=1;
for(int j=i+1;j<n;++j)
if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2; //i+1=j的情况可以不用考虑
//虽然会出现用不到的格子,但是里面是0所以不会影响计算结果
else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
}
return dp[0][n-1];
}
};
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示s字符串[i,j]所有子序列中的最长子序列的长度
2、状态转移方程
dp[i][j]:
(1)s[i]!=s[j]——>max(dp[i,j-1],dp[i+1][j])
(2)s[i]==s[j]——>
i==j 1
i+1==j 2
dp[i+1][j-1]+2
3、初始化
初始化为0 dp[i][i]=1
4、填表顺序
上到下,左到右
5、返回值
dp[0][n-1]
九、让字符串成为回文串的最小插入次数
算法原理:
1、状态表示(经验+题目要求)
dp[i][j]表示s字符串[i,j]子串,使他成为回文子串的最小插入次数
2、状态转移方程
dp[i][j]:
(1)s[i]!=s[j]——>min(dp[i,j-1],dp[i+1][j])+1
(2)s[i]==s[j]——>
i==j 0
i+1==j 0
dp[i+1][j-1]
3、初始化
初始化为0
4、填表顺序
下往上,左到右
5、返回值
dp[0][n-1]
class Solution {
public:
int minInsertions(string s) {
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n));
for(int i=n-1;i>=0;--i)
for(int j=i+1;j<n;++j)
if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
else dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;
return dp[0][n-1];
}
};
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » DP:回文串模型
发表评论 取消回复