97. Interleaving String

Description

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

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

Output: true

Example 2

Solutions

Solution 1

/**
 * Time complexity : O(2^(m+n)). m is the length of s1 and n is the length of s2.
 * Space complexity : O(m+n). The size of stack for recursive calls 
 *    can go upto m+n.
 */

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if(m+n != s3.length()) return false;
        return helper(s1, m, 0, s2, n, 0, s3, "");
    }
    
    private boolean helper(String s1, int m, int i, 
                                       String s2, int n, int j, 
                                       String s3, 
                                       String s) {
        if(s3.equals(s) && i == m && j == n) {
            return true;
        }
        boolean ans = false;
        if(i < m) {
            ans |= helper(s1, m, i+1, s2, n, j, s3, s+s1.charAt(i));
        }
        if(j < n) {
            ans |= helper(s1, m, i, s2, n, j+1, s3, s+s2.charAt(j));
        }
        return ans;
    }
}

Solution 2

Solution 3

Follow up