交错字符串操作
程序员文章站
2022-06-22 13:58:11
97. 交错字符串给定三个字符串s1、s2、s3,请你帮忙验证s3是否是由s1和s2交错组成的。输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出:true示例 2:输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出:false示例 3:输入:s1 = "", s2 = "", s3 = ""输出:true提示:0 &......
给定三个字符串
s1
、s2
、s3
,请你帮忙验证s3
是否是由s1
和s2
交错 组成的。
输入: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 <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成
基本思路:动态规划,dp[i][j]表示的是由S1的前i个字符和S2的前j个字符是否可以组成S3的前i+j个字符
- 对于dp[i][j],其最后一个字符,只能是来自于S1的第i个字符,或者S2的第j个字符
- dp[i][j]=( (s2[j-1]==s3[pos-1]) &&dp[i][j-1] || (s1[i-1]==s3[pos-1]&&dp[i-1][j]) )
注意:该问题类似于路径查找,依照下面的图(来自于leetcode 的sage),且只能向下或者向右,向右相当于选择S2[j],相下相当于选择S1[i],
bool isInterleave(string s1, string s2, string s3) {
int m=s1.size(),n=s2.size(),k=s3.size();
if(m+n!=k)
return false;
if(m*n==0)
return s1+s2==s3;
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
int pos=0;
for(int j=1;j<=n&&s3[j-1]==s2[j-1];j++){
dp[0][j]=1;
}
for(int i=1;i<=m&&s3[i-1]==s1[i-1];i++){
dp[i][0]=1;
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
pos=i+j;
if(s2[j-1]==s3[pos-1]&&dp[i][j-1]){ //只和前面的状态有关,可压缩
dp[i][j]=1;
}
if(s1[i-1]==s3[pos-1]&&dp[i-1][j]){
dp[i][j]=1;
}
}
}
return dp[m][n];
}
基本思路:状态压缩
bool isInterleave(string s1, string s2, string s3) {
int m=s1.size(),n=s2.size(),k=s3.size();
if(m+n!=k)
return false;
if(m*n==0)
return s1+s2==s3;
vector<int> dp(n+1,0);
dp[0]=1;
for(int j=1;j<=n&&s2[j-1]==s3[j-1];j++)
dp[j]=1; //初始化
for(int i=1;i<=m;i++){
dp[0]=(dp[0]&&s1[i-1]==s3[i-1]); //注意dp[0]与上一行以及当前的元素有关,要初始化
for(int j=1;j<=n;j++){
dp[j]=((dp[j-1]&&s2[j-1]==s3[i+j-1])||(dp[j]&&s1[i-1]==s3[i+j-1]));
}
}
return dp[n];
}
本文地址:https://blog.csdn.net/weixin_40306139/article/details/111122347