DEV Community

loading...
Cover image for Solution: Interleaving String

Solution: Interleaving String

seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
Updated on ・4 min read

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 1 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]
};
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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];
    }
}
Enter fullscreen mode Exit fullscreen mode

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (3)

Collapse
mellen profile image
Matt Ellen • 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;
}
Enter fullscreen mode Exit fullscreen mode

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

Collapse
seanpgallivan profile image
seanpgallivan Author

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.

Collapse
mellen profile image
Matt Ellen

Ah! Thanks for insight.