LeetCode 097 - Interleaving String - 题解/Solution

https://leetcode.com/problems/interleaving-string/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
*
* For example, Given: s1 = "aabcc", s2 = "dbbca",
*
* When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false.
*
* @author dongyuxi
*
*/
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (null == s1 && null == s2 && null == s3) {
return true;
}
if (null == s1) {
return s2.equals(s3);
}
if (null == s2) {
return s1.endsWith(s3);
}
if (null == s3) {
return false;
}
if (s3.length() != s1.length() + s2.length()) {
return false;
}
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
dp[0][0] = true;
for (int i = 1; i <= s1.length(); i++) {
dp[i][0] = dp[i - 1][0] && (s1.charAt(i - 1) == s3.charAt(i - 1));
}
for (int i = 1; i <= s2.length(); i++) {
dp[0][i] = dp[0][i - 1] && (s2.charAt(i - 1) == s3.charAt(i - 1));
}
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
|| (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
}
}
return dp[s1.length()][s2.length()];
}
}


支付宝 微信
文章目录