西安做网站的公司有哪些,做外贸网站企业,成都私人定制旅游公司排名,seo的基本步骤四个1.交错字符串 力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 给定三个字符串 s1、s2、s3#xff0c;请判断 s3 能不能由 s1 和 s2 交织#xff08;交错#xff09; 组成。 两个字符串 s 和 t 交织 的定义与过程如下#xff0c;其中每个字符串都…1.交错字符串 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 给定三个字符串 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
输出trueclass Solution {
public:bool isInterleave(string s1, string s2, string s3) {int ns1.size();int ms2.size();if(mn!s3.size())return false;s1 s1;s2 s2;s3 s3;//初始化vectorvectorbool dp(n1,vectorbool(m1));dp[0][0]true;for(int j1;jm;j){if(s2[j]s3[j])dp[0][j]true;else break;}for(int i1;in;i){if(s1[i]s3[i])dp[i][0]true;else break;}//状态转移方程for(int i1;in;i){for(int j1;jm;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;}*/dp[i][j]((dp[i-1][j]s1[i]s3[ij])||(dp[i][j-1]s2[j]s3[ij]));}}return dp[n][m];}
};
2.两个字符串的最小ASCII删除和 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 给定两个字符串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 的结果比答案更大。分析
class Solution {
public:int minimumDeleteSum(string s1, string s2) {int ns1.size(),ms2.size();vectorvectorint dp(n1,vectorint(m1));for(int i1;in;i){for(int j1;jm;j){dp[i][j]max(dp[i-1][j],dp[i][j-1]);if(s1[i-1]s2[j-1]){dp[i][j]max(dp[i][j],dp[i-1][j-1]s1[i-1]);}}}int sum10;int sum20;for(auto sh1:s1) sum1sh1;for(auto sh2:s2) sum2sh2;return sum1sum2-dp[n][m]*2;}
};
3.最长重复子数组 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 给两个整数数组 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]
输出5class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int nnums1.size();int mnums2.size();vectorvectorint dp(n1,vectorint(m1));int ret0;for(int i1;in;i){for(int j1;jm;j){if(nums1[i-1]nums2[j-1]) {dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]0;}retmax(ret,dp[i][j]);}}return ret;}
};
4.正则表达式匹配 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 给你一个字符串 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
解释.* 表示可匹配零个或多个*任意字符.。lass Solution {
public:bool isMatch(string s, string p) {int ns.size();int mp.size();vectorvectorbool dp(n1,vectorbool(m1));s s;p p;dp[0][0]true;//初始化for(int i2;im;i2){if(p[i]*)dp[0][i]true;else break;}for(int i1;in;i){//状态转移方程for(int j1;jm;j){if(s[i]p[j]dp[i-1][j-1])dp[i][j]true;else if(p[j].dp[i-1][j-1])dp[i][j]true;else if(p[j]*){dp[i][j]dp[i][j-2] || (p[j-1].||s[i]p[j-1]) dp[i-1][j];}}}return dp[n][m];//返回值}
};
5.通配符匹配 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 给你一个输入字符串 (s) 和一个字符模式 (p) 请你实现一个支持 ? 和 * 匹配规则的通配符匹配 ? 可以匹配任何单个字符。* 可以匹配任意字符序列包括空字符序列。 判定匹配成功的充要条件是字符模式必须能够 完全匹配 输入字符串而不是部分匹配。 示例 1 输入s aa, p a
输出false
解释a 无法匹配 aa 整个字符串。示例 2 输入s aa, p *
输出true
解释* 可以匹配任意字符串。示例 3 输入s cb, p ?a
输出false
解释? 可以匹配 c, 但第二个 a 无法匹配 b。class Solution {
public:bool isMatch(string s, string p) {int ns.size();int mp.size();vectorvectorbool dp(n1,vectorbool(m1));dp[0][0]true;for(int i1;im;i){if(p[i-1]*)dp[0][i]true;else break;}for(int i1;in;i){for(int j1;jm;j){if(p[j-1]*){dp[i][j]dp[i-1][j]||dp[i][j-1];}else{if(s[i-1]p[j-1]dp[i-1][j-1])dp[i][j]true;else if(p[j-1]?dp[i-1][j-1])dp[i][j]true;}}}return dp[n][m];}
};
