描述中文
给出三个字符串s1
、s2
、s3
,判断s3
是否由s1
和s2
交叉构成。
样例
样例 1:
输入:
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
输出:
true
解释:
s3 是由 s1 与 s2 交叉构成。
样例 2:
输入:
s1 = ""
s2 = ""
s3 = "1"
输出:
false
解释:
s3 不是由 s1 与 s2 交叉构成。
样例 3:
输入:
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
输出:
false
解释:
s3 不是由 s1 与 s2 交叉构成。
代码思路
动态规划。 dpi代表由s1的前i个字母和s2的前j个字母是否能构成当前i+j个字母。 然后状态转移即可。(看第i+j+1个是否能被s1的第i+1个构成或被s2的第j+1个构成)
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean [][] interleaved = new boolean[s1.length() + 1][s2.length() + 1];
interleaved[0][0] = true;
for (int i = 1; i <= s1.length(); i++) {
if(s3.charAt(i - 1) == s1.charAt(i - 1) && interleaved[i - 1][0])
interleaved[i][0] = true;
}
for (int j = 1; j <= s2.length(); j++) {
if(s3.charAt(j - 1) == s2.charAt(j - 1) && interleaved[0][j - 1])
interleaved[0][j] = true;
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if(((s3.charAt(i + j - 1) == s1.charAt(i - 1) && interleaved[i - 1][j]))
|| ((s3.charAt(i + j - 1)) == s2.charAt(j - 1) && interleaved[i][j - 1]))
interleaved[i][j] = true;
}
}
return interleaved[s1.length()][s2.length()];
}
}