Solution: Interleaving String

#algorithms #javascript #java #python

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #97 (Medium): Interleaving String

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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 they are divided into non-empty substrings 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.

Examples:

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output: true

Visual:

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = ""

Output: true

Example 1:
Input:	s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output:	true
Visual:

Example 2:
Input:	s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output:	false

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.

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

If we consider a matrix with indices (i) for s1 on one axis and indices (j) for s2 on the other, then a successful s3 can be considered a path moving from the top left to the bottom right. At each point, we either move downward (i++) by choosing the next letter from s1 or rightward (j++) by choosing the next letter from s2.

All that remains, then, is to see which vertices are possible given s3, and which ones are not. To do that, we can use a dynamic programming (DP) approach. Normally, we would establish a matrix as described above, along with a buffer row/column at the start of the matrix to provide space for previous row/column validation checks for the leading edges of our iteration. An additional row/column at the end of the matrix is also needed, since our final checks will occur only after the strings are completed.

We can reduce the space complexity of this solution from O(N * M) to just O(M), however, if rather than building a full DP matrix, we instead only keep the current rows of the matrix (dp) in memory, reiterating through it for each row. The left value will already have been calculated, and the up value will not yet have been overwritten in the current cell.

We should also remember to fill dp[1] with a true (or 1) value, representing a valid vertex at the starting position of our iteration path.

From there, we can iterate through the rows, building upon previously completed entries to check the validity of the current cell. If the cell "above" (the not-yet-overwritten dp[i] represents the same index from the row above) is valid (true or 1) and the corresponding characters of s1 and s3 match, then the current cell is valid. Similarly, if the cell to the left is valid and the corresponding characters of s2 and s3 match, then the current cell is valid.

Once we've finished iterating through i and j, a valid value in the last cell of dp will indicate that a valid path exists that matches s3, so we can just return the contents of that cell.

Time Complexity: O(N * M) where N is the length of s1 and M is the length of s2
Space Complexity: O(M) for dp

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var isInterleave = function(s1, s2, s3) {
    let n = s1.length + 2, m = s2.length + 2
    if (n + m - 4 !== s3.length) return false
    let dp = new Uint8Array(m)
    dp[1] = 1
    for (let i = 1; i < n; i++)
        for (let j = 1; j < m; j++) {
            let up = dp[j] && s1[i-2] === s3[j+i-3],
                left = dp[j-1] && s2[j-2] === s3[j+i-3]
            dp[j] = up || left
        }
    return dp[m-1]
};

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m = len(s1) + 2, len(s2) + 2
        if n + m - 4 != len(s3): return False
        dp = [0] * m
        dp[1] = 1
        for i in range(1, n):
            for j in range(1, m):
                up = dp[j] and (i < 2 or s1[i-2] == s3[j+i-3])
                left = dp[j-1] and (j < 2 or s2[j-2] == s3[j+i-3])
                dp[j] = up or left
        return dp[-1]

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length() + 2, m = s2.length() + 2;
        char[] sc1 = s1.toCharArray(), sc2 = s2.toCharArray(), sc3 = s3.toCharArray();
        if (n + m - 4 != s3.length()) return false;
        boolean[] dp = new boolean[m];
        dp[1] = true;
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++) {
                boolean up = dp[j] && (i < 2 || sc1[i-2] == sc3[j+i-3]),
                    left =dp[j-1] && (j < 2 || sc2[j-2] == sc3[j+i-3]);
                dp[j] = up || left;
            }
        return dp[m-1];
    }
}

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n = s1.length() + 2, m = s2.length() + 2;
        if (n + m - 4 != s3.length()) return false;
        vector<bool> dp(m);
        dp[1] = true;
        for (int i = 1; i < n; i++)
            for (int j = 1; j < m; j++) {
                bool up = dp[j] && (i < 2 || s1[i-2] == s3[j+i-3]),
                    left = dp[j-1] && (j < 2 || s2[j-2] == s3[j+i-3]);
               dp[j] = up || left;
            }
        return dp[m-1];
    }
};

Top comments (4)

Matt Ellen-Tsivintzeli • Jun 3 '21 • Edited

I think I have an O(N) solution, where N is the length of s3.

function isInterleaved(s1, s2, s3)
{
  let result = true;
  let currentIndex = 0;
  let last = s1;
  let other = s2;
  let lasti = 0
  let otheri = 0;
  while(currentIndex < s3.length - 1)
  {
      if(last[lasti] == s3[currentIndex])
      {
        lasti++;
        currentIndex++;
      }
      else if(other[otheri] == s3[currentIndex])
      {
        otheri++;
        let t = other;
        other = last;
        last = t;
        t = otheri;
        otheri = lasti;
        lasti = t;
        currentIndex++;
      }
      else
      {
        result = false;
        break;
      }
  }
  return result;
}

I might be missing corner cases, or have misunderstood the task 😁

seanpgallivan • Jun 3 '21

Unfortunately, this code always picks from last if the current letter matches s3. But what if the current letter of both last and other match? You would need to try both options to see if either works.

Consider s1 = "ba", s2 = "bc", s3 = "bcba". Your solution would pick the "b" from s1 but then would return a false because its only options would be the "a" from s1 or the "b" from s2 to match the "c" from s3. But clearly, we can take the entire "bc" from s2 and then the entire "ba" from s1 to match s3, so the answer should be true.

We could use a recursive or stack approach at this point to try the multiple branches, but then we'd start overlapping cases and redoing the same subproblems, which will take too long. This is the issue that dynamic programming helps to solve, by storing the results of these subproblems in a way that allows them to be accessed again, rather than resolving.