https://leetcode.cn/problems/interleaving-string/
问题的困难点在于如何使用动态规划的方法进行更新,即子问题是啥?
这道题的难点在于有三个字符串,有三个字符串,遇到这类问题肯定不能看S1,S2,只能去看S3,根据题意,
- S3由S1和S2交错组成,那么子问题应该变为S3的部分是否可以被S1/S2的部分组成
- S1 S2交错的时候 S1内部的字符串还是有顺序的,同理 S2一样
- S3的前半部分只能S1或S2的前半部分或者S1/S2整体组成
综上可得:
因为是两个字符串,我们用长度n,m 表示S1.len S2.len,其中i,j表示S1,S2的部分长度,其中0<= i <= S1.len 0<= j <= S2.len,表示组成S3的i+j位
那么F[i,j] 表示S3的前i+j位是否可以被组成,{true or false},取决于:
- 当S3[i+j -1] == S1[i-1]时,F[i,j] = F[i-1,j]
- 当S3[i+j -1] == S2[j-1]时,F[i,j] = F[i,j-1]
- F[0,0] = true 相当于 S1出0个 S2出0个组成S3的0个,那么一定为true
- F[0,j] = F[0, j-1] && S3[i+j -1] == S2[j-1]
总结:
- (F[i,j] = F[i-1, j] && S1[i-1] == S3[i+j-1]) || (F[i,j] = F[i,j -1] && S2[j-1] == S3[i+j-1]), 条件: 0< i < S1.len & 0 < j < S2.len
- F[0][0] = true 条件:i ==0 j == 0
- F[0][j] = F[0][j-1] && S2[j-1] == S3[i+j-1]; 条件:i== 0; 0 < j < S2.len
- F[i][0] = F[i-1]0] && S1[i-1] == S3[i+j-1]; 条件: 0< i < S1.len; j ==0
同步注意 输入的边界条件:
S1 S2 S3可能为空
public boolean isInterleave(String s1, String s2, String s3) {
boolean F[][] = new boolean[s1.length()+1][s2.length()+1];
if (s1.length() + s2.length() != s3.length()) {
return false;
}
if (s1.length() == 0 || s2.length() == 0) {
return s1.equals(s3) || s2.equals(s3);
}
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 && j == 0) {
F[i][j] = true;
} else if (i == 0) {
F[i][j] = F[i][j - 1] && (s3.charAt(i + j - 1) == s2.charAt(j - 1));
} else if (j == 0) {
F[i][j] = F[i - 1][j] && (s3.charAt(i + j - 1) == s1.charAt(i - 1));
} else {
F[i][j] = (F[i][j - 1] && (s3.charAt(i + j - 1) == s2.charAt(j - 1))) ||
F[i - 1][j] && (s3.charAt(i + j - 1) == s1.charAt(i - 1));
}
}
}
return F[s1.length()][s2.length()];
}
问题1:没有计算好数组的长度
image.png
问题2:没有边界条件 当S1/S2/S3都为空的时候
image.png
问题3: F存储数据的位置和真实字符串的问题相互转换
image.png
