题目描述
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.
代码
dp[i][j]表示s1[0…i-1]和s2[0…j-1]能表示s3[0…i+j-1]，即s1的前i个字符和s2的前j个字符能按规则表示s3的前i+j个字符。则：
dp[i][j] = dp[i-1][j] && s1[i-1] == s3[i+j-1] 或者 dp[i][j-1] && s2[j-1] == s3[i+j-1]
结果为：
dp[s1.length()][s2.length()]
边界情况：
i=0,j=0:dp[i][j] = true，表示s1、s2、s3都未空字符串
i=0 dp[i][j] = dp[i][j-1] && s2[j-1] == s3[i+j-1]
j=0 dp[i][j] = dp[i-1][j] && s1[i-1] == s3[i+j-1]
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
|
public class Solution{
public boolean (String s1, String s2, String s3) {
if(s1.length() + s2.length() != s3.length()) return false;
boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
for(int i = 0; i <= s1.length(); i++){
for(int j = 0; j <= s2.length(); j++){
if(i == 0 && j == 0) {
dp[i][j] = true;
}else if(i == 0){
dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
}else if(j == 0){
dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1);
}else{
dp[i][j] = (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1)) || (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1));
}
}
}
return dp[s1.length()][s2.length()];
}
}
|
近期评论