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

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

Output: false

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

/**
 * Time complexity : O(m*n). dp array of size m*n is filled.
 * Space complexity : O(m*n). 2D dp of size (m+1)*(n+1) is required. m and n are 
 *    the lengths of strings s1 and s2 respectively.
 */

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length(), p = s3.length();
        if(m+n != p) return false;
        
        char[] s1Chars = s1.toCharArray();
        char[] s2Chars = s2.toCharArray();
        char[] s3Chars = s3.toCharArray();
        boolean[][] dp = new boolean[m+1][n+1];
        
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0) {
                    dp[i][j] = true;
                } else if(i == 0) {
                    dp[i][j] = dp[i][j-1] && s2Chars[j-1] == s3Chars[i+j-1];
                } else if(j == 0) {
                    dp[i][j] = dp[i-1][j] && s1Chars[i-1] == s3Chars[i+j-1];
                } else {
                    dp[i][j] = (dp[i-1][j] && s1Chars[i-1] == s3Chars[i+j-1]) || 
                                (dp[i][j-1] && s2Chars[j-1] == s3Chars[i+j-1]);
                }
            }
        }
        
        return dp[m][n];
    }
}

Solution 3

/**
 * Time complexity : O(m*n). dp array of size n is filled m times.
 * Space complexity : O(n). n is the length of the string s1.
 */

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;
        
        boolean[] dp = new boolean[n+1];
        
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0) {
                    dp[j] = true;
                } else if(i == 0) {
                    dp[j] = dp[j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
                } else if(j == 0) {
                    dp[j] = dp[j] && s1.charAt(i-1) == s3.charAt(i+j-1);
                } else {
                    dp[j] = (dp[j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || 
                                (dp[j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
                }
            }
        }
        
        return dp[n];
    }
}

Follow up