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 and s3 didn't match but characters in s2 and s3 match, or
• if characters in s2 and s3 didn't match but characters in s1 and s3 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].