DEV Community

Cover image for Solution: Interleaving String
seanpgallivan
seanpgallivan

Posted on • Edited on

2 1

Solution: Interleaving String

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

Tiugo image

Modular, Fast, and Built for Developers

CKEditor 5 gives you full control over your editing experience. A modular architecture means you get high performance, fewer re-renders and a setup that scales with your needs.

Start now

Top comments (4)

Collapse
 
mellen profile image
Matt Ellen-Tsivintzeli • 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

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-Tsivintzeli

Ah! Thanks for insight.

Collapse
 
ahmedsiam72 profile image
AhmedSiam72

I found that solution very popular and helpful: https://www.youtube.com/watch?v=sfP64T6SmaY&ab_channel=EricProgramming

Neon image

Next.js applications: Set up a Neon project in seconds

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Get started →

👋 Kindness is contagious

Explore a trove of insights in this engaging article, celebrated within our welcoming DEV Community. Developers from every background are invited to join and enhance our shared wisdom.

A genuine "thank you" can truly uplift someone’s day. Feel free to express your gratitude in the comments below!

On DEV, our collective exchange of knowledge lightens the road ahead and strengthens our community bonds. Found something valuable here? A small thank you to the author can make a big difference.

Okay