Leetcode 97. Interleaving String
Problem Description
Given three strings, s1, s2, and s3, determine if s3 is formed by the interleaving of s1 and s2. An interleaving is when the characters from s1 and s2 are in the same order in s3 but may not be continuous.
Walkthrough an Example
If s1 = "aabcc"
, s2 = "dbbca"
, and s3 = "aadbbcbcac"
. We can see that we can interleave s1
and s2
to get s3
as follows:
- Pick 'a' from
s1
, s3 becomes "adbbcbcac" - Pick 'a' from
s1
, s3 becomes "dbbcbcac" - Pick 'd' from
s2
, s3 becomes "bbcbcac" - Pick 'b' from
s2
, s3 becomes "bcbcac" - Pick 'b' from
s2
, s3 becomes "cbcac" - Pick 'c' from
s1
, s3 becomes "bcac" - Pick 'c' from
s1
, s3 becomes "ac" - Pick 'a' from
s2
, s3 becomes "c" - Pick 'c' from
s1
, s3 becomes ""
By the time we've picked all characters from s1
and s2
, s3
is empty. This confirms that s3
is indeed formed by interleaving s1
and s2
.
Approach
A dynamic programming approach will be used to solve this task. A table will be created where dp[i][j]
represents whether s3 up to position i+j is a valid interleaving of s1
up to position i
and s2
up to position j
.
The first row and column of table is initialized where dp[i][0]
is true if s1
is valid interleaving of s3
upto i position otherwise false.
The rest table will be filled up by condition:
- if characters in
s1
ands3
didn't match but characters ins2
ands3
match, or - if characters in
s2
ands3
didn't match but characters ins1
ands3
match.
i.e., 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]))
.
We will return the result from dp[m][n]
representing that s3
is interleaving of s1
and s2
or not.
Python Solution
1 2python 3class Solution: 4 def isInterleave(self, s1: str, s2: str, s3: str) -> bool: 5 m, n = len(s1), len(s2) 6 if m + n != len(s3): 7 return False 8 9 dp = [[False for _ in range(n+1)] for _ in range(m+1)] 10 dp[0][0] = True 11 12 for i in range(1, m+1): 13 if s1[i-1] == s3[i-1]: 14 dp[i][0] = dp[i-1][0] 15 16 for i in range(1, n+1): 17 if s2[i-1] == s3[i-1]: 18 dp[0][i] = dp[0][i-1] 19 20 for i in range(1, m+1): 21 for j in range(1, n+1): 22 dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1]) 23 24 return dp[m][n]
In this Python solution, a 2D boolean dynamic-programming table dp
is created and initially set to False. It then iterates through s1
, s2
, and s3
to determine whether s3
can be formed by interleaving s1
and s2
.
Java Solution
1 2java 3public class Solution { 4 public boolean isInterleave(String s1, String s2, String s3) { 5 int m = s1.length(); 6 int n = s2.length(); 7 if (m + n != s3.length()) return false; 8 9 boolean[][] dp = new boolean[m+1][n+1]; 10 dp[0][0] = true; 11 12 for (int i = 1; i <= m; i++) 13 dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1); 14 15 for (int i = 1; i <= n; i++) 16 dp[0][i] = dp[0][i-1] && s2.charAt(i-1) == s3.charAt(i-1); 17 18 for (int i = 1; i <= m; i++) 19 for (int j = 1; j <= n; j++) 20 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)); 21 22 return dp[m][n]; 23 } 24}
The Java solution is essentially the same as the Python one, but with Java syntax and specific classes and methods related to Java.
JavaScript Solution
1 2javascript 3class Solution { 4 isInterleave(s1, s2, s3) { 5 const m = s1.length, n = s2.length; 6 if (m + n !== s3.length) return false; 7 8 let dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(false)); 9 dp[0][0] = true; 10 11 for (let i = 1; i <= m; i++) 12 dp[i][0] = dp[i-1][0] && s1[i-1] === s3[i-1]; 13 14 for (let i = 1; i <= n; i++) 15 dp[0][i] = dp[0][i-1] && s2[i-1] === s3[i-1]; 16 17 for (let i = 1; i <= m; i++) 18 for (let j = 1; j <= n; j++) 19 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]); 20 21 return dp[m][n]; 22 } 23}
The JavaScript solution bears many similarities to the Python and Java solutions, but with its own distinct syntax and idioms. The approach and logic of the code remain unchanged.
C++ Solution
1 2c++ 3class Solution { 4public: 5 bool isInterleave(string s1, string s2, string s3) { 6 int m = s1.length(); 7 int n = s2.length(); 8 if (m + n != s3.length()) return false; 9 10 vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false)); 11 dp[0][0] = true; 12 13 for (int i = 1; i <= m; i++) 14 dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]; 15 16 for (int i = 1; i <= n; i++) 17 dp[0][i] = dp[0][i-1] && s2[i-1] == s3[i-1]; 18 19 for (int i = 1; i <= m; i++) 20 for (int j = 1; j <= n; j++) 21 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]); 22 23 return dp[m][n]; 24 } 25};
The C++ solution is the same as the previous ones but implemented using C++ syntax and STD library.
C# Solution
1 2csharp 3public class Solution { 4 public bool IsInterleave(string s1, string s2, string s3) { 5 int m = s1.Length; 6 int n = s2.Length; 7 if (m + n != s3.Length) return false; 8 9 bool[,] dp = new bool[m+1, n+1]; 10 dp[0, 0] = true; 11 12 for (int i = 1; i <= m; i++) 13 dp[i, 0] = dp[i-1, 0] && s1[i-1] == s3[i-1]; 14 15 for (int i = 1; i <= n; i++) 16 dp[0, i] = dp[0, i-1] && s2[i-1] == s3[i-1]; 17 18 for (int i = 1; i <= m; i++) 19 for (int j = 1; j <= n; j++) 20 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]); 21 22 return dp[m, n]; 23 } 24}
For C#, the boolean dynamic programming array is created using two-dimensional array syntax. The remainder of the solution follows the same logic as the other languages.## Ruby Solution
1 2ruby 3def is_interleave(s1, s2, s3) 4 m, n = s1.size, s2.size 5 return false if m + n != s3.size 6 7 dp = Array.new(m+1) { Array.new(n+1, false) } 8 dp[0][0] = true 9 10 for i in 1..m 11 dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1] 12 end 13 14 for i in 1..n 15 dp[0][i] = dp[0][i - 1] && s2[i - 1] == s3[i - 1] 16 end 17 18 for i in 1..m 19 for j in 1..n 20 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]) 21 end 22 end 23 24 dp[m][n] 25end
This Ruby solution follows a similar approach to the ones above: using dynamic programming to build a 2D boolean array, dp
, where each cell indicates if s3
can be formed by interleaving a prefix of s1
and a prefix of s2
. It first checks if the lengths of s1
, s2
, and s3
are consistent; if not, it immediately returns false
.
It initializes the first row and column of dp
and then fills in the rest using a nested for
loop. The final result is obtained from dp[m][n]
.
Go Solution
1 2go 3func isInterleave(s1 string, s2 string, s3 string) bool { 4 m, n := len(s1), len(s2) 5 if m+n != len(s3) { 6 return false 7 } 8 9 dp := make([][]bool, m+1) 10 for i := range dp { 11 dp[i] = make([]bool, n+1) 12 } 13 dp[0][0] = true 14 15 for i := 1; i <= m; i++ { 16 dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1] 17 } 18 19 for i := 1; i <= n; i++ { 20 dp[0][i] = dp[0][i-1] && s2[i-1] == s3[i-1] 21 } 22 23 for i := 1; i <= m; i++ { 24 for j := 1; j <= n; j++ { 25 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]) 26 } 27 } 28 29 return dp[m][n] 30}
The Go solution is similar to the previous solutions. We create a 2D boolean slice dp
where dp[i][j]
indicates if s3
up to position i+j
is an interleave of s1
up to i
and s2
up to j
. We initialize the slice and fill it up based on the matching conditions of the characters in s1
, s2
, and s3
. The final result is stored in dp[m][n]
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.