97. Interleaving String LeetCode Solution

Last updated: February 14, 2025

In this guide, you will get 97. Interleaving String LeetCode Solution with the best time and space complexity. The solution to Interleaving String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Interleaving String solution in C++
Interleaving String solution in Java
Interleaving String solution in Python
Additional Resources

97. Interleaving String LeetCode Solution image

Problem Statement of Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n – m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + … or t1 + s1 + t2 + s2 + t3 + s3 + …

Note: a + b is the concatenation of strings a and b.

Example 1:

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = “aa” + “bc” + “c”, and s2 into s2 = “dbbc” + “a”.
Interleaving the two splits, we get “aa” + “dbbc” + “bc” + “a” + “c” = “aadbbcbcac”.
Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = “”, s2 = “”, s3 = “”
Output: true

Constraints:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lowercase English letters.

Follow up: Could you solve it using only O(s2.length) additional memory space?

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

97. Interleaving String LeetCode Solution in C++

class Solution {
 public:
  bool isInterleave(string s1, string s2, string s3) {
    const int m = s1.length();
    const int n = s2.length();
    if (m + n != s3.length())
      return false;

    // dp[i][j] := true if s3[0..i + j) is formed by the interleaving of
    // s1[0..i) and s2[0..j)
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
    dp[0][0] = true;

    for (int i = 1; i <= m; ++i)
      dp[i][0] = dp[i - 1][0] && s1[i - 1] == s3[i - 1];

    for (int j = 1; j <= n; ++j)
      dp[0][j] = dp[0][j - 1] && s2[j - 1] == s3[j - 1];

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++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];

    return dp[m][n];
  }
};
/* code provided by PROGIEZ */

97. Interleaving String LeetCode Solution in Java

class Solution {
  public boolean isInterleave(String s1, String s2, String s3) {
    final int m = s1.length();
    final int n = s2.length();
    if (m + n != s3.length())
      return false;

    // dp[i][j] := true if s3[0..i + j) is formed by the interleaving of
    // s1[0..i) and s2[0..j)
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;

    for (int i = 1; i <= m; ++i)
      dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);

    for (int j = 1; j <= n; ++j)
      dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        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[m][n];
  }
}
// code provided by PROGIEZ

97. Interleaving String LeetCode Solution in Python

class Solution:
  def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    m = len(s1)
    n = len(s2)
    if m + n != len(s3):
      return False

    # dp[i][j] := true if s3[0..i + j) is formed by the interleaving of
    # s1[0..i) and s2[0..j)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    for i in range(1, m + 1):
      dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]

    for j in range(1, n + 1):
      dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]

    for i in range(1, m + 1):
      for j in range(1, n + 1):
        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])

    return dp[m][n]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents