LeetCode - Interleaving String
Problem description
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
1
2
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Analysis
The first thought is to use backtrack to get all possible interleaving strings and check if s3 is in it. However, this method will get a TLE.
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
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
HashSet<String> set = new HashSet<>();
int len = s1.length() + s2.length();
if (s3.length() != len){
return false;
}
backtrack(set, s1, s2, new StringBuilder(), 0, 0);
return set.contains(s3);
}
void backtrack(HashSet<String> set, String s1, String s2, StringBuilder sb, int i, int j){
if (i == s1.length() & j == s2.length()){
set.add(sb.toString());
return;
}
else if (i == s1.length()){
set.add(sb.toString() + s2.substring(j));
}
else if (j == s2.length()){
set.add(sb.toString() + s1.substring(i));
}
else{
sb.append(s1.charAt(i));
backtrack(set, s1, s2, sb, i+1, j);
sb.deleteCharAt(sb.length() - 1);
sb.append(s2.charAt(j));
backtrack(set, s1, s2, sb, i, j+1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
And then I come up with a solution using two pointers.
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
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len = s1.length() + s2.length();
if (s3.length() != len){
return false;
}
return test(s1, s2, s3, 0 , 0 , 0);
}
boolean test(String s1, String s2, String s3, int i, int j, int index){
if (i == s1.length() && j == s2.length()){
return true;
}
else if (i == s1.length()){
return s3.substring(index).equals(s2.substring(j));
}
else if (j == s2.length()){
return s3.substring(index).equals(s1.substring(i));
}
else{
boolean isS1Match = s1.charAt(i) == s3.charAt(index);
boolean isS2Match = s2.charAt(j) == s3.charAt(index);
return (isS1Match && test(s1, s2, s3, i+1, j, index+1)) || (isS2Match && test(s1, s2, s3, i, j+1, index+1));
}
}
}
But this solution runs in low performance with TC O(2 m+n). m is the length of s1 and n is the length of s2.
So we introduce a memo to save all computed result.
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
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len = s1.length() + s2.length();
if (s3.length() != len){
return false;
}
int[][] memo = new int[s1.length() + 1][s2.length()+1];
return test(s1, s2,s3, 0 , 0 , 0, memo);
}
boolean test(String s1, String s2, String s3, int i, int j, int index, int[][] memo){
if (memo[i][j] != 0){
return memo[i][j]> 0;
}
if (i == s1.length() && j == s2.length()){
return true;
}
else if (i == s1.length()){
boolean res = s3.substring(index).equals(s2.substring(j));
memo[i][j] = res ? 1:-1;
return res;
}
else if (j == s2.length()){
boolean res = s3.substring(index).equals(s1.substring(i));
memo[i][j] = res ? 1:-1;
return res;
}
else{
boolean isS1Match = s1.charAt(i) == s3.charAt(index);
boolean isS2Match = s2.charAt(j) == s3.charAt(index);
boolean res = (isS1Match && test(s1, s2, s3, i+1, j, index+1, memo)) || (isS2Match && test(s1, s2, s3, i, j+1, index+1, memo));
memo[i][j] = res ? 1:-1;
return res;
}
}
}
And if we can use recursion with memorization, we can also use DP.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.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 - 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()];
}
}
What to improve
- When do recursion, remember to check if we can use memorization to reduce TC.