You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
54 lines
1.1 KiB
54 lines
1.1 KiB
2 years ago
|
package class04;
|
||
|
|
|
||
|
|
// 本题测试链接 : https://leetcode.com/problems/interleaving-string/
|
||
|
|
public class Code07_InterleavingString {
|
||
|
|
|
||
|
|
public static boolean isInterleave(String s1, String s2, String s3) {
|
||
|
|
if (s1 == null || s2 == null || s3 == null) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
char[] str1 = s1.toCharArray();
|
||
|
|
char[] str2 = s2.toCharArray();
|
||
|
|
char[] str3 = s3.toCharArray();
|
||
|
|
if (str3.length != str1.length + str2.length) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
|
||
|
|
dp[0][0] = true;
|
||
|
|
for (int i = 1; i <= str1.length; i++) {
|
||
|
|
if (str1[i - 1] != str3[i - 1]) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
dp[i][0] = true;
|
||
|
|
}
|
||
|
|
for (int j = 1; j <= str2.length; j++) {
|
||
|
|
if (str2[j - 1] != str3[j - 1]) {
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
dp[0][j] = true;
|
||
|
|
}
|
||
|
|
for (int i = 1; i <= str1.length; i++) {
|
||
|
|
for (int j = 1; j <= str2.length; j++) {
|
||
|
|
if (
|
||
|
|
(str1[i - 1] == str3[i + j - 1] && dp[i - 1][j])
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
||
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
(str2[j - 1] == str3[i + j - 1] && dp[i][j - 1])
|
||
|
|
|
||
|
|
|
||
|
|
) {
|
||
|
|
dp[i][j] = true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
return dp[str1.length][str2.length];
|
||
|
|
}
|
||
|
|
|
||
|
|
}
|