文章目录
- 1、分割回文串 IV
- 2、分割回文串 II
- 3、最长回文子序列
- 4、让字符串成为回文串的最少插入次数
- 5、最长公共子序列
- 6、不相交的线
1、分割回文串 IV
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。
当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。
class Solution {
public:
bool checkPartitioning(string s) {
int n=s.size();
vector<vector<bool>> dp(n,vector<bool>(n,false));
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;
}
}
for(int i=1;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(dp[0][i-1]&&dp[i][j-1]&&dp[j][n-1])
return true;
}
}
return false;
}
};
2、分割回文串 II
给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的 最少分割次数 。
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);
}
}
}
return dp[n-1];
}
};
3、最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
class Solution {
public:
//s[i]==s[j]三种情况 i==j 1 i+1=j 2 i<j dp[i+1][j-1]+2
//s[i]!=s[j] max(dp[i][j-1],dp[i+1][j])
int longestPalindromeSubseq(string s) {
int n=s.size();
vector<vector<int>> dp(n,vector<int>(n));
//i<=j必须
for(int i=n-1;i>=0;i--)
{
dp[i][i]=1;//单拎出来，后面省点事i==j
for(int j=i+1;j<n;j++)
{
if(s[i]==s[j])
{
dp[i][j]=dp[i+1][j-1]+2;
}
else
{
dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
}
}
}
return dp[0][n-1];
}
};
4、让字符串成为回文串的最少插入次数
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
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];
}
};
5、最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n=text1.size();
int m=text2.size();
vector<vector<int>> dp(n+1,vector<int>(m+1));
text1=" "+text1;//引入空串会方便我们的初始化
text2=" "+text2;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(text1[i]==text2[j])//空串方便了这里
{
dp[i][j]=dp[i-1][j-1]+1;//这里会发生越界所以在创建数组时多创建了空间
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
};
6、不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n=nums1.size();
int m=nums2.size();
vector<vector<int>> dp(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(nums1[i-1]==nums2[j-1])//空串方便了这里
{
dp[i][j]=dp[i-1][j-1]+1;//这里会发生越界所以在创建数组时多创建了空间
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
};
