广州网站推广工具,莆田制作公司网站,长沙网络公司网站,企业网络营销策划书算法沉淀——动态规划之两个数组的 dp 01.正则表达式匹配02.交错字符串03.两个字符串的最小ASCII删除和04.最长重复子数组 01.正则表达式匹配
题目链接#xff1a;https://leetcode.cn/problems/regular-expression-matching/
给你一个字符串 s 和一个字符规律 p#xff0c… 算法沉淀——动态规划之两个数组的 dp 01.正则表达式匹配02.交错字符串03.两个字符串的最小ASCII删除和04.最长重复子数组 01.正则表达式匹配
题目链接https://leetcode.cn/problems/regular-expression-matching/
给你一个字符串 s 和一个字符规律 p请你来实现一个支持 . 和 * 的正则表达式匹配。
. 匹配任意单个字符* 匹配零个或多个前面的那一个元素
所谓匹配是要涵盖 整个 字符串 s的而不是部分字符串。
示例 1
输入s aa, p a
输出false
解释a 无法匹配 aa 整个字符串。示例 2:
输入s aa, p a*
输出true
解释因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 a。因此字符串 aa 可被视为 a 重复了一次。示例 3
输入s ab, p .*
输出true
解释.* 表示可匹配零个或多个*任意字符.。 提示
1 s.length 201 p.length 20s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母以及字符 . 和 *。保证每次出现字符 * 时前面都匹配到有效的字符
思路
在处理字符串匹配的动态规划问题时通常按照以下步骤进行 状态表达 选取第一个字符串 [0, i] 区间以及第二个字符串 [0, j] 区间作为研究对象结合题目的要求定义状态表达。在这道题中我们定义状态表达为 dp[i][j]表示字符串 p 的 [0, j] 区间和字符串 s 的 [0, i] 区间是否可以匹配。 状态转移方程 根据最后一个位置的元素结合题目要求进行分类讨论 当 s[i] p[j] 或 p[j] . 时两个字符串匹配上了当前的一个字符只能从 dp[i-1][j-1] 中看当前字符前面的两个子串是否匹配继承上个状态中的匹配结果dp[i][j] dp[i-1][j-1]。当 p[j] * 时匹配策略有两种选择 一种选择是p[j-1]* 匹配空字符串相当于这两个字符都匹配了一个寂寞直接继承状态 dp[i][j-2]dp[i][j] dp[i][j-2]。另一种选择是p[j-1]* 向前匹配 1 ~ n 个字符直至匹配上整个 s 串。相当于从 dp[k][j-2] (0 k i 且 s[k]~s[i] p[j-1]) 中所有匹配情况中选择性继承可以成功的情况dp[i][j] dp[k][j-2] (0 k i)。 当 p[j] 不是特殊字符且不与 s[i] 相等时无法匹配。综上状态转移方程为 当 s[i] p[j] 或 p[j] . 时dp[i][j] dp[i-1][j-1]。当 p[j] * 时状态转移方程为dp[i][j] dp[i][j-2] || dp[i-1][j]。 初始化 dp 数组的值表示是否匹配初始化整个数组为 false。由于需要用到前一行和前一列的状态初始化第一行和第一列。 dp[0][0] 表示两个空串是否匹配初始化为 true。第一行表示 s 为空串 p 串全部字符表示为 .* 或 任一字符*此时相当于空串匹配上空串将所有前导为 任一字符* 的 p 子串和空串的 dp 值设为 true。第一列表示 p 为空串不可能匹配上 s 串跟随数组初始化即可。 填表顺序 从上往下填每一行每一行从左往右。 返回值 根据状态表达返回 dp[m][n] 的值。
代码
class Solution {
public:bool isMatch(string s, string p) {int ms.size(),np.size();s s,p p;vectorvectorbool dp(m1,vectorbool(n1));dp[0][0]true;for(int i2;in;i2)if(p[i]*) dp[0][i]true;else break;for(int i1;im;i)for(int j1;jn;j){if(p[j]*) dp[i][j]dp[i][j-2]||(p[j-1].||p[j-1]s[i])dp[i-1][j];else dp[i][j](p[j]s[i]||p[j].)dp[i-1][j-1];}return dp[m][n];}
};02.交错字符串
题目链接https://leetcode.cn/problems/interleaving-string/
给定三个字符串 s1、s2、s3请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下其中每个字符串都会被分割成若干 非空 子字符串
s s1 s2 ... snt t1 t2 ... tm|n - m| 1交错 是 s1 t1 s2 t2 s3 t3 ... 或者 t1 s1 t2 s2 t3 s3 ...
注意a b 意味着字符串 a 和 b 连接。
示例 1
输入s1 aabcc, s2 dbbca, s3 aadbbcbcac
输出true示例 2
输入s1 aabcc, s2 dbbca, s3 aadbbbaccc
输出false示例 3
输入s1 , s2 , s3
输出true提示
0 s1.length, s2.length 1000 s3.length 200s1、s2、和 s3 都由小写英文字母组成
思路
状态表达 对于两个字符串的动态规划问题首先考虑选取第一个字符串的 [0, i] 区间和第二个字符串的 [0, j] 区间作为研究对象。定义状态表达 dp[i][j]表示字符串 s1 中 [1, i] 区间内的字符和字符串 s2 中 [1, j] 区间内的字符是否能够交错组成字符串 s3 中 [1, i j] 区间内的字符。 状态转移方程 根据两个区间上的最后一个字符进行分类讨论 如果 s3[i j] s1[i]说明交错后的字符串的最后一个字符和 s1 的最后一个字符匹配了。这时需要判断整个字符串是否能够交错组成即 dp[i][j] dp[i - 1][j]。如果 s3[i j] s2[j]说明交错后的字符串的最后一个字符和 s2 的最后一个字符匹配了。这时需要判断整个字符串是否能够交错组成即 dp[i][j] dp[i][j - 1]。如果两者的末尾字符都不等于 s3 最后一个位置的字符说明不可能是两者的交错字符串dp[i][j] 保持不变。 初始化 初始化第一个位置dp[0][0] true因为空串与空串能够构成空串。初始化第一行dp[0][j]表示 s1 是空串需要判断与 s2 的交错情况。如果 s2[j - 1] s3[j - 1] 且 dp[0][j - 1] 为真则 dp[0][j] true。初始化第一列dp[i][0]表示 s2 是空串需要判断与 s1 的交错情况。如果 s1[i - 1] s3[i - 1] 且 dp[i - 1][0] 为真则 dp[i][0] true。 填表顺序 从上往下逐行填表每一行从左往右。 返回值 根据状态表达 dp[m][n] 的值其中 m 和 n 分别是 s1 和 s2 的长度判断是否能够交错组成字符串 s3。
代码
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int ms1.size(),ns2.size();if(s3.size()!mn) return false;s1 s1,s2 s2,s3 s3;vectorvectorbool dp(m1,vectorbool(n1));dp[0][0]true;for(int i1;in;i) if(s2[i]s3[i]) dp[0][i] true;else break;for(int i1;im;i)if(s1[i]s3[i]) dp[i][0] true;else break;for(int i1;im;i)for(int j1;jn;j)dp[i][j](s1[i]s3[ij]dp[i-1][j])||(s2[j]s3[ij]dp[i][j-1]);return dp[m][n];}
};03.两个字符串的最小ASCII删除和
题目链接https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/
给定两个字符串s1 和 s2返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
示例 1:
输入: s1 sea, s2 eat
输出: 231
解释: 在 sea 中删除 s 并将 s 的值(115)加入总和。
在 eat 中删除 t 并将 116 加入总和。
结束时两个字符串相等115 116 231 就是符合条件的最小和。示例 2:
输入: s1 delete, s2 leet
输出: 403
解释: 在 delete 中删除 dee 字符串变成 let
将 100[d]101[e]101[e] 加入总和。在 leet 中删除 e 将 101[e] 加入总和。
结束时两个字符串都等于 let结果即为 100101101101 403 。
如果改为将两个字符串转换为 lee 或 eet我们会得到 433 或 417 的结果比答案更大。提示:
0 s1.length, s2.length 1000s1 和 s2 由小写英文字母组成
思路 状态表达 dp[i][j] 表示字符串 s1 的 [0, i] 区间以及字符串 s2 的 [0, j] 区间内的所有的子序列中公共子序列的 ASCII 最大和。 状态转移方程 根据最后一个位置的元素进行情况讨论 如果 s1[i] s2[j]说明当前字符可以被加入到公共子序列中此时 dp[i][j] dp[i - 1][j - 1] s1[i]。 如果 s1[i] ! s2[j]此时有三种可能 在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j] 区间内找公共子序列的最大和即 dp[i][j] dp[i - 1][j]。在 s1 的 [0, i] 区间以及 s2 的 [0, j - 1] 区间内找公共子序列的最大和即 dp[i][j] dp[i][j - 1]。在 s1 的 [0, i - 1] 区间以及 s2 的 [0, j - 1] 区间内找公共子序列的最大和即 dp[i][j] dp[i - 1][j - 1]。 由于前两种情况包含了第三种情况因此只需考虑前两种情况下的最大值。 初始化 引入空串后扩大了状态表的规模方便初始化。需要注意下标的映射关系以及确保后续填表的正确性。当 s1 和 s2 为空时没有长度所以第一行和第一列的值初始化为 0。 填表顺序 从上往下逐行填表每一行从左往右。 返回值 先找到 dp[m][n]即最大公共 ASCII 和。统计两个字符串的 ASCII 码和 sum。返回 sum - 2 * dp[m][n]。
代码
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int ms1.size(),ns2.size();vectorvectorint dp(m1,vectorint(n1));for(int i1;im;i)for(int j1;jn;j){dp[i][j]max(dp[i][j-1],dp[i-1][j]);if(s1[i-1]s2[j-1]) dp[i][j]max(dp[i][j],dp[i-1][j-1]s1[i-1]);}int sum0;for(auto s:s1) sums;for(auto s:s2) sums;return sum-dp[m][n]*2;}
};04.最长重复子数组
题目链接https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1
输入nums1 [1,2,3,2,1], nums2 [3,2,1,4,7]
输出3
解释长度最长的公共子数组是 [3,2,1] 。示例 2
输入nums1 [0,0,0,0,0], nums2 [0,0,0,0,0]
输出5提示
1 nums1.length, nums2.length 10000 nums1[i], nums2[i] 100
思路
状态表达 dp[i][j] 表示以第一个数组的第 i 位置为结尾以及第二个数组的第 j 位置为结尾时两个数组的最长重复子数组的长度。 状态转移方程 当 nums1[i] nums2[j] 时说明当前位置两个数组的元素相等此时最长重复子数组的长度应该等于 1 加上除去最后一个位置时以 i - 1, j - 1 为结尾的最长重复子数组的长度即 dp[i][j] 1 dp[i - 1][j - 1]。 初始化 为了处理越界的情况添加了一行和一列使 dp 数组的下标从 1 开始。第一行表示第一个数组为空因此没有重复子数组所以其中的值设置为 0。第一列同理。 填表顺序 根据状态转移方程从上往下逐行填表每一行从左往右。 返回值 根据状态表达需要返回 dp 表中的最大值。
代码
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int mnums1.size(),nnums2.size();vectorvectorint dp(m1,vectorint(n1));int ret0;for(int i1;im;i)for(int j1;jn;j)if(nums1[i-1]nums2[j-1]) dp[i][j]dp[i-1][j-1]1, retmax(ret,dp[i][j]);return ret;}
};
