Interleaving String

MEDIUM

Description

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 = s₁ + s₂ + ... + s_n
t = t₁ + t₂ + ... + t_m
|n - m| <= 1
The interleaving is s₁ + t₁ + s₂ + t₂ + s₃ + t₃ + ... or t₁ + s₁ + t₂ + s₂ + t₃ + s₃ + ...

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?

Approaches

Checkout 4 different approaches to solve Interleaving String. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Recursion

This approach uses a simple recursive function to explore all possible ways of forming s3 by picking characters from s1 and s2. It directly models the decision process: at each character of s3, we decide whether to match it with the current character of s1 or s2. If a character in s3 matches both, we explore both possibilities recursively.

Algorithm

The core idea is to use a recursive function, say check(i, j), which determines if the rest of s3 (from index i+j) can be formed by the rest of s1 (from index i) and the rest of s2 (from index j).
First, perform a preliminary check: if s1.length() + s2.length() != s3.length(), it's impossible to form s3, so return false.
Base Case: If we have successfully traversed all of s1 and s2 (i.e., i == s1.length() and j == s2.length()), it means we have successfully formed s3. Return true.
Recursive Step: At the current state (i, j), we are trying to match s3.charAt(i+j).
- If s1.charAt(i) matches s3.charAt(i+j), we make a recursive call check(i + 1, j). If this call returns true, we have found a valid interleaving.
- If s2.charAt(j) matches s3.charAt(i+j), we make a recursive call check(i, j + 1). If this call returns true, we have also found a valid interleaving.
- The result for check(i, j) is true if either of the possible recursive calls returns true.
- If neither character matches or if the subsequent recursive calls return false, this path is invalid.

The method involves a helper function that takes two pointers, i for s1 and j for s2, indicating the number of characters already used from each string. The current character to be matched in s3 is at index k = i + j.

If the current character of s3 matches the character at s1[i], we recursively call the function with i+1. If it matches s2[j], we recursively call with j+1. If it matches both, we try both paths and return true if either path leads to a solution. The recursion stops when we have successfully used all characters from both s1 and s2.

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        return check(s1, s2, s3, 0, 0);
    }

    private boolean check(String s1, String s2, String s3, int i, int j) {
        // Base case: if we have reached the end of all strings
        if (i == s1.length() && j == s2.length()) {
            return true;
        }

        boolean match1 = false;
        if (i < s1.length() && s1.charAt(i) == s3.charAt(i + j)) {
            match1 = check(s1, s2, s3, i + 1, j);
        }

        // If the first path was successful, no need to check the second
        if (match1) {
            return true;
        }

        boolean match2 = false;
        if (j < s2.length() && s2.charAt(j) == s3.charAt(i + j)) {
            match2 = check(s1, s2, s3, i, j + 1);
        }

        return match2;
    }
}

Complexity Analysis

Time Complexity: O(2^(m+n))Space Complexity: O(m + n)

Pros and Cons

Pros:

Simple to understand and implement.
Directly translates the problem definition into code.

Cons:

Extremely inefficient due to a large number of redundant computations for the same subproblems (i.e., the same i and j values are computed multiple times through different recursive paths).
Will likely result in a 'Time Limit Exceeded' error on most online judges for non-trivial inputs.

Code Solutions

Checking out 4 solutions in different languages for Interleaving String. Click on different languages to view the code.

public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        int m = s1.Length, n = s2.Length;
        if (m + n != s3.Length) {
            return false;
        }
        bool[] f = new bool[n + 1];
        f[0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                int k = i + j - 1;
                if (i > 0) {
                    f[j] &= s1[i - 1] == s3[k];
                }
                if (j > 0) {
                    f[j] |= (f[j - 1] & s2[j - 1] == s3[k]);
                }
            }
        }
        return f[n];
    }
}

Video Solution

Watch the video walkthrough for Interleaving String

Patterns:

Dynamic Programming

Data Structures:

String

Companies:

Amazon |Apple |Goldman Sachs |Microsoft |