Home / string / Interleaved Strings

Interleaved Strings

Given three strings A, B and C your task is to complete the function isInterleave which returns true if C is an interleaving of A and B else returns false. C is said to be interleaving A and B, if it contains all characters of A and B and order of all characters in individual strings is preserved.
Example 1:
Input:
str1 = YX, str2 = X, str3 = XXY
Output: 0
Explanation: XXY is not interleaving
of YX and X
Example 2:
Input:
str1 = XY, str2 = X, str3 = XXY
Output: 1
Explanation: XXY is interleaving of
XY and X.

lets use dynamic programming to solve this question:
Algorithm:
  1. Create a DP array (matrix) of size M*N, where m is size of first string and n is the size of second string. Initialize the matrix to false.
  2. If the sum of sizes of smaller strings is not equal to the size of larger string then return false and break the array as they cant be the interleaved to form the larger string.
  3. Run a nested loop the outer loop from 0 to m and the inner loop from 0 to n. Loop counters are i and j.
  4. If the values of i and j are both zeroes then mark dp[i][j] as true. If the value of i is zero and j is non zero and the j-1 character of B is equal to j-1 character of C the assign dp[i][j] as dp[i][j-1] and similarly if j is 0 then match i-1 th character of C and A and if it matches then assign dp[i][j] as dp[i-1][j].
  5. Take three characters x, y, z as (i-1)th character of A and (j-1)th character of B and (i + j – 1)th character of C.
  6. if x matches with z and y does not match with z then assign dp[i][j] as dp[i-1][j] similarly if x is not equal to z and y is equal to z then assign dp[i][j] as dp[i][j-1]
  7. if x is equal to y and y is equal to z then assign dp[i][j] as bitwise OR of dp[i][j-1] and dp[i-1][j].
  8. return value of dp[m][n].
c++ program:


// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

bool isInterleave(string A, string B, string C);
int main() {
 int t;
 cin>>t;
 while(t--)
 {
  string a,b,c;
  cin>>a;
  cin>>b;
  cin>>c;
  cout<<isInterleave(a,b,c)<<endl;
 }
 // your code goes here
 return 0;
}// } Driver Code Ends


/*You are required to complete this method */
bool isInterleave(string str1, string str2, string str3) 
{  int n=str1.length();
int m=str2.length();
    bool dp[n+1][m+1];
    
      for(int i=0; i <=n; i++)
            for(int j=0; j <=m; j++)
            dp[i][j]=0;
        
        if(n + m != str3.length()){
            return false;
        }
        
        for(int i=0; i <=n; i++){
            for(int j=0; j <=m; j++){
                int l = i + j -1;
                if(i == 0 && j == 0){
                    dp[i][j] = true;
                }
                else if(i == 0){
                    if(str3[l] == str2[j-1]){
                        dp[i][j] = dp[i][j-1];
                    }
                }
                else if(j == 0){
                    if(str1[i-1] == str3[l]){
                        dp[i][j] = dp[i-1][j];
                    }
                }
                else{
                    dp[i][j] = (str1[i-1] == str3[l] ? dp[i-1][j] : false) || (str2[j-1] == str3[l] ? dp[i][j-1] : false);
                }
            }
        }
        return dp[n][m];
}


this question is taken from :https://practice.geeksforgeeks.org/
darkmode