给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/interleaving-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
首先得判断s1与s2的长度之和是否等于s3的长度,若不相等则s1和s2怎么组合都不可能匹配出s3。
该问题可以转化为每次从s1或者s2中顺序取一个元素,最终直到s1, s2取完若能够组成s3,则认为s3可以由s1, s2交错组成。我们的每步操作只要选择s1或者s2即可。
定义dp[i] [j] 为s1从i开始,s2从j开始能否匹配上s3。
转移方程:
若s1的当前元素等于s3的当前元素,判断从s1的下一个元素和s2当前元素开始能否匹配上s3的下一个元素开始的字符串,若能匹配上,则当前位置选择s1可以完成匹配;
若s2的当前元素等于s3的当前元素,判断从s2的下一个元素和s1当前元素开始能否匹配上s3的下一个元素开始的字符串,若能匹配上,则当前位置选择s2可以完成匹配;
否则就不能完成匹配。
baseline:
上式中,M为s1的长度,N为s2的长度。
第一个式子s1,s2都用完了,s3也完了,返回true
第二个式子时s2用完了,s1还有,此时需要判断s1剩下的元素能否与s3剩下的元素完成匹配
第二个式子时s1用完了,s2还有,此时需要判断s2剩下的元素能否与s3剩下的元素完成匹配
代码如下:
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length()){
return false;
}
int M = s1.length();
int N = s2.length();
// dp[i][j] 为s1从i开始,s2从j开始能否匹配上 s3从i + j开始
boolean[][] dp = new boolean[M + 1][N + 1];
// init
dp[M][N] = true;
// s2没了
for(int i = M - 1; i >= 0; i--){
if(s1.charAt(i) == s3.charAt(N + i)){
dp[i][N] = true;
}else{
break;
}
}
for(int j = N - 1; j >= 0; j--){
if(s2.charAt(j) == s3.charAt(M + j)){
dp[M][j] = true;
}else{
break;
}
}
for(int i = M - 1; i >= 0; i--){
for(int j = N - 1; j >= 0; j--){
dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i + 1][j]) || (s2.charAt(j) == s3.charAt(i + j) && dp[i][j + 1]);
}
}
return dp[0][0];
}
}