wordpress导航站主题,视觉品牌网站建设,室内设计大学排名榜,公司专业网站建设目录 一、最长公共子序列
二、不同的子序列
三、通配符匹配
四、正则表达式匹配
五、两个字符串的最小ASCII删除和
六、最长重复子数组
七、交错字符串 一、最长公共子序列
最长公共子序列 第一步#xff1a;确定状态表示
dp[i][j]#xff1a;表示字符串 s1 的 [0确定状态表示
dp[i][j]表示字符串 s1 的 [0i] 区间以及字符串 s2 的[0j] 区间内所有子序列中最长公共子序列的长度。
第二步推出状态转移方程 第三步初始化dp表
关于字符串的 dp 问题我们需要考虑空串的情况比如 s1 选一个空串s2 选一个空串其实也属于是一个公共子序列不过公共子序列长度为0。
我们可以在原始 dp 表上多加一行一列第0行表示第一个字符串为空第0列表示第二个字符串为空。 让dp表多加了一行和一列后我们需要注意dp表的下标和字符串下标的对应关系。
解题代码
class Solution
{
public:int longestCommonSubsequence(string s1, string s2) {int m s1.size(), n s2.size();vectorvectorint dp(m1, vectorint(n1));for(int i 1; i m; i){for(int j 1; j n; j){if(s1[i-1] s2[j-1])dp[i][j] dp[i-1][j-1] 1;elsedp[i][j] max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]));}}return dp[m][n];}
}; 二、不同的子序列
不同的子序列 第一步确定状态表示
dp[i][j]表示s字符串 [0i]区间内所有子序列中有多少个t字符串 [0j] 区间内的子串。
第二步推出状态转移方程 第三步初始化dp表。
我们需要考虑空串的情况比如 s1 选一个空串s2 选一个空串其实也属于是一个公共子序列。
第一行表示 s 字符串为空串s 如果是空串t 只有是空串才能在 s 中找到 t。第一列表示 t 字符串为空串t 如果是空串s 不管是什么字符串它里面都有一个空串。因此第一列应该全都是1。 解题代码
class Solution
{
public:int numDistinct(string s, string t){int m s.size(), n t.size();vectorvectordouble dp(m1, vectordouble(n1));for(int i 0; i m; i)dp[i][0] 1;for(int i 1; i m; i){for(int j 1; j n; j){dp[i][j] dp[i-1][j];if(s[i-1] t[j-1])dp[i][j] dp[i-1][j-1];}}return dp[m][n];}
}; 三、通配符匹配
通配符匹配 第一步 确定状态表示
dp[i][j]表示p[0i] 区间内的子串能否匹配 s[0j] 区间内的子串。
第二步推出状态转移方程 第三步初始化dp表
如果s是空字符串p字符串前面出现 ’ * ‘ 可以匹配空串但是 ’ * ‘ 之后如果出现其他字符了后面不管有多少个’ * 都不能匹配了。 dp[i][j]表示p[0i] 区间内的子串能否匹配 s[0j] 区间内的子串。题目要求是整个字符串因此返回dp[m][n]m是s的长度n是p的长度。
解题代码
class Solution
{
public:bool isMatch(string s, string p) {int m p.size(), n s.size();vectorvectorbool dp(m1, vectorbool(n1, false));dp[0][0] true;for(int i 1; i m; i){if(p[i-1] *)dp[i][0] true;elsebreak;}for(int i 1; i m; i){for(int j 1; j n; j){if(p[i-1] ?)dp[i][j] dp[i-1][j-1];else if(p[i-1] *)dp[i][j] dp[i][j-1] || dp[i-1][j];else{if(p[i-1] s[j-1] dp[i-1][j-1])dp[i][j] true;}}}return dp[m][n];}
}; 四、正则表达式匹配
正则表达式匹配 第一步确定状态表示
dp[i][j]表示 p[0i] 区间内的子串能否匹配 s[0j] 区间内的字符串。
第二步推出状态转移方程 第三步初始化dp表
dp表上面多加一行表示p是空串左边多加一列表示s是空串。接下来看看里面值应该填什么。
对于第一行如果p是空串s也是空串肯定能匹配所以第一行第一个空格还是true。
后续如果 p 是空串s不是空串肯定匹配不上所以第一行后续都是false。 解题代码
class Solution
{
public:bool isMatch(string s, string p) {int m p.size(), n s.size();vectorvectorbool dp(m1, vectorbool(n1));dp[0][0] true;s s;p p;for(int i 2; i m; i){if(p[i] ! * p[i-1] ! *)break;if(p[i] * p[i-1] ! *)dp[i][0] true;}for(int i 1; i m; i){for(int j 1; j n; j){if(p[i] a p[i] z){if(p[i] s[j] dp[i-1][j-1] true)dp[i][j] true;}else if(p[i] .)dp[i][j] dp[i-1][j-1];else{if(p[i-1] .)dp[i][j] dp[i-2][j] || dp[i][j-1];elsedp[i][j] dp[i-2][j] || (s[j] p[i-1] dp[i][j-1]);}}}return dp[m][n];}
}; 五、两个字符串的最小ASCII删除和
两个字符串的最小ASCII删除和 预处理本道题是让我们找使两个字符串相等所需删除字符的ASCII值最小。而最开始的两个字符串的ASCII值总和是不变的那么我们只需要找到两个字符串相同后其ASCII值最大那么删除的字符的ASCII值一定就是最小的。
所以说该问题就转化成了求两个字符串的所有公共子序列里面ASCII值的最大和。
第一步确定状态表示
dp[i][j]表示字符串 s1 的 [0i] 区间以及字符串 s2 的 [0j] 区间内的所有公共子序列中 ASCII值最大和。
第二步推出状态转移方程
对于s1[0i]区间和s2[0j]区间的公共子序列有四种情况即
有s1[i]有s2[j]
有s1[i]没有s2[j]
没有s1[i]有s2[j]
没有s1[i]没有s2[j]
情况四可以包含在情况二中。 第三步初始化dp表 第四步确定返回值
状态表示求的是两个字符串的区间里面公共子序列的ASCII值最大和。
而题目要求使两个字符串相等所需删除字符的ASCII值的最小和 。所以可以这样做
1、找到两个字符串中公共子序列的Ascll 最大和dp[m][n]。
2、统计两个字符串中ASCII值总和sum。
3、sum - dp[m][n] * 2。
解题代码
class Solution
{
public:int minimumDeleteSum(string s1, string s2) {int m s1.size(), n s2.size();vectorvectorint dp(m1, vectorint(n1));for(int i 1; i m; i){for(int j 1; j n; j){if(s1[i-1] s2[j-1])dp[i][j] dp[i-1][j-1] s1[i-1];dp[i][j] max(dp[i][j], max(dp[i][j-1], dp[i-1][j]));}}int sum 0;for(auto x : s1)sum x;for(auto x : s2)sum x;return sum - 2 * dp[m][n];}
}; 六、最长重复子数组
最长重复子数组 第一步确定状态表示
dp[i][j]表示数组 nums1 中以 i 位置元素为结尾的所有的子数组以及数组 nums2 中以 j 位置元素为结尾的所有子数组中最长公共子数组的长度。
第二步推出状态转移方程 第三步初始化dp表 填写顺序根据状态转移方程。从上往下填写每一行。 最后的返回值是 dp 表里面的最大值。
解题代码
class Solution
{
public:int findLength(vectorint nums1, vectorint nums2) {int m nums1.size(), n nums2.size();vectorvectorint dp(m1, vectorint(n1));int ret 0;for(int i 1; i m; i){for(int j 1; j n; j){if(nums1[i-1] nums2[j-1])dp[i][j] dp[i-1][j-1] 1;ret max(ret, dp[i][j]);}}return ret;}
}; 七、交错字符串
交错字符串 预处理为了下标对应我们给每个字符串的前面都加上一个空格字符。
第一步确定状态表示
dp[i][j]表示s1[1i]区间内的字符串和s2[1j]区间内的字符串能不能拼成s3[1ij]区间内的字符串。
第二步推出状态转移方程 第三步初始化dp表 解题代码
class Solution
{
public:bool isInterleave(string s1, string s2, string s3) {int m s1.size(), n s2.size();if(mn ! s3.size())return false;s1 s1;s2 s2;s3 s3;vectorvectorbool dp(m1, vectorbool(n1));dp[0][0] true;for(int i 1; i n; i){if(s2[i] s3[i])dp[0][i] true;elsebreak;}for(int i 1; i m; i){if(s1[i] s3[i])dp[i][0] true;elsebreak;}for(int i 1; i m; i){for(int j 1; j n; j){if(s1[i] s3[ij] dp[i-1][j])dp[i][j] true;else if(s2[j] s3[ij] dp[i][j-1])dp[i][j] true;}}return dp[m][n];}
};
