|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -/** |
4 | | - * 97. Interleaving String |
5 | | - * |
6 | | - * Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. |
7 | | - * For example, |
8 | | - * Given: |
9 | | - * s1 = "aabcc", |
10 | | - * s2 = "dbbca", |
11 | | - * When s3 = "aadbbcbcac", return true. |
12 | | - * When s3 = "aadbbbaccc", return false. |
13 | | - */ |
14 | 3 | publicclass_97 { |
15 | | -publicstaticclassSolution1 { |
16 | | -publicbooleanisInterleave(Strings1,Strings2,Strings3) { |
17 | | -intm =s1.length(); |
18 | | -intn =s2.length(); |
19 | | -if (m +n !=s3.length()) { |
20 | | -returnfalse; |
21 | | - } |
| 4 | +publicstaticclassSolution1 { |
| 5 | +publicbooleanisInterleave(Strings1,Strings2,Strings3) { |
| 6 | +intm =s1.length(); |
| 7 | +intn =s2.length(); |
| 8 | +if (m +n !=s3.length()) { |
| 9 | +returnfalse; |
| 10 | +} |
22 | 11 |
|
23 | | -boolean[][]dp =newboolean[m +1][n +1]; |
| 12 | +boolean[][]dp =newboolean[m +1][n +1]; |
24 | 13 |
|
25 | | -dp[0][0] =true; |
| 14 | +dp[0][0] =true; |
26 | 15 |
|
27 | | -for (inti =0;i <m;i++) { |
28 | | -if (s1.charAt(i) ==s3.charAt(i)) { |
29 | | -dp[i +1][0] =true; |
30 | | - }else { |
31 | | -//if one char fails, that means it breaks, the rest of the chars won't matter any more. |
32 | | -//Mian and I found one missing test case on Lintcode: ["b", "aabccc", "aabbbcb"] |
33 | | -//if we don't break, here, Lintcode could still accept this code, but Leetcode fails it. |
34 | | -break; |
35 | | - } |
36 | | - } |
| 16 | +for (inti =0;i <m;i++) { |
| 17 | +if (s1.charAt(i) ==s3.charAt(i)) { |
| 18 | +dp[i +1][0] =true; |
| 19 | +}else { |
| 20 | +//if one char fails, that means it breaks, the rest of the chars won't matter any more. |
| 21 | +//Mian and I found one missing test case on Lintcode: ["b", "aabccc", "aabbbcb"] |
| 22 | +//if we don't break, here, Lintcode could still accept this code, but Leetcode fails it. |
| 23 | +break; |
| 24 | +} |
| 25 | +} |
37 | 26 |
|
38 | | -for (intj =0;j <n;j++) { |
39 | | -if (s2.charAt(j) ==s3.charAt(j)) { |
40 | | -dp[0][j +1] =true; |
41 | | - }else { |
42 | | -break; |
43 | | - } |
44 | | - } |
| 27 | +for (intj =0;j <n;j++) { |
| 28 | +if (s2.charAt(j) ==s3.charAt(j)) { |
| 29 | +dp[0][j +1] =true; |
| 30 | +}else { |
| 31 | +break; |
| 32 | +} |
| 33 | +} |
45 | 34 |
|
46 | | -for (inti =1;i <=m;i++) { |
47 | | -for (intj =1;j <=n;j++) { |
48 | | -intk =i +j -1; |
49 | | -dp[i][j] = (s1.charAt(i -1) ==s3.charAt(k) &&dp[i -1][j]) |
50 | | - || (s2.charAt(j -1) ==s3.charAt(k) &&dp[i][j -1]); |
51 | | - } |
52 | | - } |
| 35 | +for (inti =1;i <=m;i++) { |
| 36 | +for (intj =1;j <=n;j++) { |
| 37 | +intk =i +j -1; |
| 38 | +dp[i][j] = (s1.charAt(i -1) ==s3.charAt(k) &&dp[i -1][j]) |
| 39 | +|| (s2.charAt(j -1) ==s3.charAt(k) &&dp[i][j -1]); |
| 40 | +} |
| 41 | +} |
53 | 42 |
|
54 | | -returndp[m][n]; |
| 43 | +returndp[m][n]; |
| 44 | + } |
55 | 45 | } |
56 | | - } |
57 | 46 | } |