97. 交错字符串 给定三个字符串 s1、s2、s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + … + sn t = t1 + t2 + … + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + … 注意:a + b 意味着字符串 a 和 b 连接。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size()) return false;
vector<bool> v(s2.size() + 1, false);
vector<vector<bool>> dp(s1.size() + 1, v);
dp[0][0] = true;
for(int i = 1;i <= s1.size(); ++i)
{
dp[i][0] = s1[i - 1] == s3[i - 1] && dp[i - 1][0];
}
for(int j = 1;j <= s2.size(); ++j)
{
dp[0][j] = s2[j - 1] == s3[j - 1] && dp[0][j - 1];
}
dp[0][0] = true;
for(int i = 1;i <= s1.size(); ++i)
{
for(int j = 1;j <= s2.size(); ++j)
{
if((s1[i - 1] == s3[i + j - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && dp[i][j - 1]))
dp[i][j] = true;
}
}
return dp[s1.size()][s2.size()];
}
};
712. 两个字符串的最小ASCII删除和 给定两个字符串s1 和 s2,返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
vector<int> v(s2.size() + 1, 0);
vector<vector<int>> dp(s1.size() + 1, v);
//dp[i][j]表示以i-1为结尾的字符串s1,和以j-1为结尾的字符串s2的公共子序列字符之和
for(int i = 1;i <= s1.size(); ++i)
{
for(int j = 1;j <= s2.size(); ++j)
{
if(s1[i - 1] == s2[j - 1])
{
dp[i][j] = dp[i - 1][j - 1] + s1[i - 1];
}
else
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int sum = 0;
for(auto& e : s1)
{
sum += e;
}
for(auto& e : s2)
{
sum += e;
}
return sum - 2 * dp[s1.size()][s2.size()];
}
};
718. 最长重复子数组 给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<int> v(nums2.size() + 1, 0);
vector<vector<int>> dp(nums1.size() + 1, v);
int ret = 0;
for(int i = 1;i <= nums1.size(); ++i)
{
for(int j = 1;j <= nums2.size(); ++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;
}
};
今天是算法练习的第14天。 行成于思,毁于随,继续加油。 来源:力扣(LeetCode),著作权归领扣网络所有。 如果本篇文章对你有所启发的话,希望可以多多支持作者,谢谢大家!