DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

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

Example 1:

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

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.

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

SOLUTION:

class Solution:
    def isLeave(self, s1, s2, s3, i, j, k, m, n, p):
        if (i, j, k) in self.cache:
            return self.cache[(i,j,k)]
        if i >= m or j >= n or k >= p:
            if i >= m:
                res = s2[j:] == s3[k:]
                self.cache[(i,j,k)] = res
                return res
            if j >= n:
                res = s1[i:] == s3[k:]
                self.cache[(i,j,k)] = res
                return res
            self.cache[(i,j,k)] = False
            return False
        if s1[i] == s3[k] and self.isLeave(s1, s2, s3, i + 1, j, k + 1, m, n, p):
            self.cache[(i,j,k)] = True
            return True
        if s2[j] == s3[k] and self.isLeave(s1, s2, s3, i, j + 1, k + 1, m, n, p):
            self.cache[(i,j,k)] = True
            return True
        self.cache[(i,j,k)] = False
        return False

    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m = len(s1)
        n = len(s2)
        p = len(s3)
        self.cache = {}
        return self.isLeave(s1, s2, s3, 0, 0, 0, m, n, p)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)