Open In App

Check if a String is Interleaving of Other Two

Last Updated : 23 Jul, 2025
Suggest changes
Share
Like Article
Like
Report

Give three strings s1, s2 and s3, determine if s3 is formed by interleaving s1 and s2.
A string s3 is an interleaving of s1 and s2 if:

  • It contains all characters of s1 and s2 while preserving their relative order.
  • Characters from s1 and s2 appear in s3 in the same order as in their original strings.
  • The length of s3 equals the combined length of s1 and s2.

Example

Input: s1 = "AAB", s2 = "AAC", s3 = "AAAABC",
Output: true
Explanation: The string "AAAABC" has all characters of the other two strings and in the same order.

Input: s1 = "AB", s2 = "C", s3 = "ACB",
Output: true
Explanation: s3 has all characters of s1 and s2 and retains order of characters of s1.

Input: s1 = "YX", s2 = "X", s3 = "XXY"
Output: false
Explanation: "XXY " is not interleaved of "YX" and "X". The strings that can be formed are YXX and XYX

Table of Content

[Naive Approach] Using Recursion - O(2^(m+n)) Time and O(m+n) Space

The main idea is to recursively check whether s3 can be formed by choosing characters from s1 and s2, ensuring we maintain the correct order. To do so, initialise three variable i, j, and k to store the index of string s1, s2, and s3 respectively. To handle all cases, the following possibilities need to be considered.

  • If the first character of s3 matches the first character of s1, we move one character ahead in s1 and s3 and recursively check.
  • If the first character of s3 matches the first character of s2, we move one character ahead in s2 and s3 and recursively check.
  • If none of the two characters match, return false.
  • If any of the above function returns true or s1, s2 and s3 are empty then return true else return false.
C++ 
// Cpp program to check if Check if a String is // Interleaving of Other Two using recursion #include <iostream> using namespace std; // i amnd j are indexes in s1 and s2 respectively bool isILRec(string &s1, string &s2, string &s3, int i, int j) {  int k = i + j;  // If all strings are fully traversed  if (i == s1.size() && j == s2.size() && k == s3.size())  return true;  // If any of the above mentioned two  // possibilities then return true  // otherwise return false.  bool a = (i < s1.size()) && (s3[k] == s1[i]) && isILRec(s1, s2, s3, i + 1, j);  bool b = (j < s2.size()) && (s3[k] == s2[j]) && isILRec(s1, s2, s3, i, j + 1);  return a || b; } bool isInterleave(string &s1, string &s2, string &s3) {  // A basic condition that must be ensured  if (s1.size() + s2.size() != s3.size())  return false;  return isILRec(s1, s2, s3, 0, 0); } int main() {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  cout << (isInterleave(s1, s2, s3) ? "true" : "false") << endl;  return 0; }
Java 
// Java program to check if Check if a String is // Interleaving of Other Two using recursion class GfG {  // i and j are indexes in s1 and s2 respectively  static boolean isILRec(String s1, String s2, String s3,  int i, int j)  {  int k = i + j;  // If all strings are fully traversed  if (i == s1.length() && j == s2.length()  && k == s3.length())  return true;  // If any of the above mentioned two  // possibilities then return true  // otherwise return false.  boolean a = (i < s1.length())  && (s3.charAt(k) == s1.charAt(i))  && isILRec(s1, s2, s3, i + 1, j);  boolean b = (j < s2.length())  && (s3.charAt(k) == s2.charAt(j))  && isILRec(s1, s2, s3, i, j + 1);  return a || b;  }  static boolean isInterleave(String s1, String s2,  String s3)  {  // A basic condition that must be ensured  if (s1.length() + s2.length() != s3.length())  return false;  return isILRec(s1, s2, s3, 0, 0);  }  public static void main(String[] args)  {  String s1 = "AAB";  String s2 = "AAC";  String s3 = "AAAABC";  System.out.println(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
Python 
# Python program to check if Check if a String is # Interleaving of Other Two using recursion def isILRec(s1, s2, s3, i, j): # i and j are indexes in s1 and s2 respectively k = i + j # If all strings are fully traversed if i == len(s1) and j == len(s2) and k == len(s3): return True # If any of the above mentioned two # possibilities then return true # otherwise return false. a = (i < len(s1)) and (s3[k] == s1[i]) and isILRec(s1, s2, s3, i + 1, j) b = (j < len(s2)) and (s3[k] == s2[j]) and isILRec(s1, s2, s3, i, j + 1) return a or b def isInterleave(s1, s2, s3): # A basic condition that must be ensured if len(s1) + len(s2) != len(s3): return False return isILRec(s1, s2, s3, 0, 0) if __name__ == "__main__": s1 = "AAB" s2 = "AAC" s3 = "AAAABC" print("true" if isInterleave(s1, s2, s3) else "false")
C# 
// C# program to check if Check if a String is // Interleaving of Other Two using recursion using System; class GfG {  // i and j are indexes in s1 and s2 respectively  static bool isILRec(string s1, string s2, string s3,  int i, int j)  {  int k = i + j;  // If all strings are fully traversed  if (i == s1.Length && j == s2.Length  && k == s3.Length)  return true;  // If any of the above mentioned two  // possibilities then return true  // otherwise return false.  bool a = (i < s1.Length) && (s3[k] == s1[i])  && isILRec(s1, s2, s3, i + 1, j);  bool b = (j < s2.Length) && (s3[k] == s2[j])  && isILRec(s1, s2, s3, i, j + 1);  return a || b;  }  static bool isInterleave(string s1, string s2,  string s3)  {  // A basic condition that must be ensured  if (s1.Length + s2.Length != s3.Length)  return false;  return isILRec(s1, s2, s3, 0, 0);  }  static void Main(string[] args)  {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  Console.WriteLine(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
JavaScript 
// JavaScript program to check if Check if a String is // Interleaving of Other Two using recursion function isILRec(s1, s2, s3, i, j) {  // i and j are indexes in s1 and s2 respectively  let k = i + j;  // If all strings are fully traversed  if (i === s1.length && j === s2.length  && k === s3.length)  return true;  // If any of the above mentioned two  // possibilities then return true  // otherwise return false.  let a = (i < s1.length) && (s3[k] === s1[i])  && isILRec(s1, s2, s3, i + 1, j);  let b = (j < s2.length) && (s3[k] === s2[j])  && isILRec(s1, s2, s3, i, j + 1);  return a || b; } function isInterleave(s1, s2, s3) {  // A basic condition that must be ensured  if (s1.length + s2.length !== s3.length)  return false;  return isILRec(s1, s2, s3, 0, 0); } // Driver Code let s1 = "AAB"; let s2 = "AAC"; let s3 = "AAAABC"; console.log(isInterleave(s1, s2, s3) ? "true" : "false");

Output
true

[Better Approach 1] Using Top-Down DP - O(m*n) Time and O(n*m) Space

The above recursive solution certainly has many overlapping sub-problems. For example, if we consider s1 = "AAB”, s2 = “AAC” and s3 = “AAAABC” and draw a recursion tree, there will be many overlapping subproblems. Therefore, like any other typical Dynamic Programming problems, we can solve it by creating a table and store results of sub-problems. Below is a memoization based solution that creates a 2D memo array.

We optimize the recursive approach using memoization to avoid redundant calculations.

We track indices i and j in s1 and s2, respectively, ensuring that characters match s3 at index k = i + j. If either s1[i] or s2[j] matches s3[k], we recursively move forward while storing results in a memo table to prevent recomputation.

The base case ensures that when all strings are fully traversed, we return true. This approach significantly reduces the time complexity compared to plain recursion.

Steps to implement the above idea:

  • Check if s3 length is equal to s1 + s2, return false if not.
  • Create a (m+1) x (n+1) table memo[][] with -1 to store results. The value of memo[i][j] is going to be 1 if s3[0..i + j-1] is an interleaving of s1[0..i-1] and s2[0..j-1], else 0.
  • If memo[i][j] is not -1, return the stored result to avoid recomputation.
  • Try both possibilities (matching s1[i] or s2[j] with s3[k]) and store the result in memo[i][j].
  • Return true if all strings are fully traversed, otherwise return false.
C++ 
// C++ program to check if Check if a String is // Interleaving of Other Two using memoization #include <bits/stdc++.h> using namespace std; bool isILRec(string &s1, string &s2, string &s3, int i, int j, vector<vector<int>> &memo) {  int k = i + j;  int m = s1.size(), n = s2.size();  // Base case: If all strings are fully traversed  if (i == m && j == n && k == s3.size())  return true;  // If we have already solved this subproblem,  // return the stored result  if (memo[i][j] != -1)  {  return memo[i][j];  }  // Check if next characcter of s1 maatchs with  // with the next one of s3  bool a = (i < m && s1[i] == s3[k]) && isILRec(s1, s2, s3, i + 1, j, memo);  // Check if next characcter of s2 maatchs with  // with the next one of s3  bool b = (j < n && s2[j] == s3[k]) && isILRec(s1, s2, s3, i, j + 1, memo);  return memo[i][j] = a || b; } bool isInterleave(string &s1, string &s2, string &s3) {  int m = s1.size(), n = s2.size();  // A basic condition that must be ensured  if (m + n != s3.size())  return false;  // Intiialize memo with -1 and make Recursive function call  vector<vector<int>> memo(m + 1, vector<int>(n + 1, -1));  return isILRec(s1, s2, s3, 0, 0, memo); } int main() {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  cout << (isInterleave(s1, s2, s3) ? "true" : "false") << endl;  return 0; }
Java 
// Java program to check if Check if a String is // Interleaving of Other Two using memoization import java.util.Arrays; class GfG {  // i and j are indexes in s1 and s2 respectively  static boolean isILRec(String s1, String s2, String s3,  int i, int j, int[][] memo)  {  int k = i + j;  int m = s1.length();  int n = s2.length();  // Base case: If all strings are fully traversed  if (i == m && j == n && k == s3.length())  return true;  // If we have already solved this subproblem,  // return the stored result  if (memo[i][j] != -1) {  return memo[i][j] == 1;  }  // Check if next character of s1 matches with  // with the next one of s3  boolean a = false;  if (i < m && s1.charAt(i) == s3.charAt(k)) {  a = isILRec(s1, s2, s3, i + 1, j, memo);  }  // Check if next character of s2 matches with  // with the next one of s3  boolean b = false;  if (j < n && s2.charAt(j) == s3.charAt(k)) {  b = isILRec(s1, s2, s3, i, j + 1, memo);  }  memo[i][j] = a || b ? 1 : 0;  return a || b;  }  static boolean isInterleave(String s1, String s2,  String s3)  {  int m = s1.length();  int n = s2.length();  // A basic condition that must be ensured  if (m + n != s3.length())  return false;  // Initialize memo with -1 and make Recursive  // function call  int[][] memo = new int[m + 1][n + 1];  for (int[] row : memo)  Arrays.fill(row, -1);  return isILRec(s1, s2, s3, 0, 0, memo);  }  public static void main(String[] args)  {  String s1 = "AAB";  String s2 = "AAC";  String s3 = "AAAABC";  System.out.println(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
Python 
# Python program to check if Check if a String is # Interleaving of Other Two using memoization def isILRec(s1, s2, s3, i, j, memo): # i and j are indexes in s1 and s2 respectively k = i + j m = len(s1) n = len(s2) # Base case: If all strings are fully traversed if i == m and j == n and k == len(s3): return True # If we have already solved this subproblem, # return the stored result if memo[i][j] != -1: return memo[i][j] == 1 # Check if next character of s1 matches with # with the next one of s3 a = False if i < m and s1[i] == s3[k]: a = isILRec(s1, s2, s3, i + 1, j, memo) # Check if next character of s2 matches with # with the next one of s3 b = False if j < n and s2[j] == s3[k]: b = isILRec(s1, s2, s3, i, j + 1, memo) memo[i][j] = 1 if a or b else 0 return a or b def isInterleave(s1, s2, s3): # A basic condition that must be ensured m = len(s1) n = len(s2) if m + n != len(s3): return False # Initialize memo with -1 and make Recursive function call memo = [[-1 for _ in range(n + 1)] for _ in range(m + 1)] return isILRec(s1, s2, s3, 0, 0, memo) if __name__ == "__main__": s1 = "AAB" s2 = "AAC" s3 = "AAAABC" print("true" if isInterleave(s1, s2, s3) else "false")
C# 
// C# program to check if Check if a String is // Interleaving of Other Two using memoization using System; class GfG {  // i and j are indexes in s1 and s2 respectively  static bool isILRec(string s1, string s2, string s3,  int i, int j, int[, ] memo)  {  int k = i + j;  int m = s1.Length;  int n = s2.Length;  // Base case: If all strings are fully traversed  if (i == m && j == n && k == s3.Length)  return true;  // If we have already solved this subproblem,  // return the stored result  if (memo[i, j] != -1)  return memo[i, j] == 1;  // Check if next character of s1 matches with  // with the next one of s3  bool a = false;  if (i < m && s1[i] == s3[k])  a = isILRec(s1, s2, s3, i + 1, j, memo);  // Check if next character of s2 matches with  // with the next one of s3  bool b = false;  if (j < n && s2[j] == s3[k])  b = isILRec(s1, s2, s3, i, j + 1, memo);  memo[i, j] = (a || b) ? 1 : 0;  return a || b;  }  static bool isInterleave(string s1, string s2,  string s3)  {  int m = s1.Length;  int n = s2.Length;  // A basic condition that must be ensured  if (m + n != s3.Length)  return false;  // Initialize memo with -1 and make Recursive  // function call  int[, ] memo = new int[m + 1, n + 1];  for (int i = 0; i <= m; i++)  for (int j = 0; j <= n; j++)  memo[i, j] = -1;  return isILRec(s1, s2, s3, 0, 0, memo);  }  static void Main(string[] args)  {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  Console.WriteLine(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
JavaScript 
// Javascript program to check if Check if a String is // Interleaving of Other Two using memoization function isILRec(s1, s2, s3, i, j, memo) {  // i and j are indexes in s1 and s2 respectively  let k = i + j;  let m = s1.length;  let n = s2.length;  // Base case: If all strings are fully traversed  if (i === m && j === n && k === s3.length)  return true;  // If we have already solved this subproblem,  // return the stored result  if (memo[i][j] !== -1) {  return memo[i][j] === 1;  }  // Check if next character of s1 matches with  // with the next one of s3  let a = false;  if (i < m && s1[i] === s3[k]) {  a = isILRec(s1, s2, s3, i + 1, j, memo);  }  // Check if next character of s2 matches with  // with the next one of s3  let b = false;  if (j < n && s2[j] === s3[k]) {  b = isILRec(s1, s2, s3, i, j + 1, memo);  }  memo[i][j] = (a || b) ? 1 : 0;  return a || b; } function isInterleave(s1, s2, s3) {  // A basic condition that must be ensured  let m = s1.length;  let n = s2.length;  if (m + n !== s3.length)  return false;  // Initialize memo with -1 and make Recursive function  // call  let memo = Array(m + 1).fill(null).map(  () => Array(n + 1).fill(-1));  return isILRec(s1, s2, s3, 0, 0, memo); } // Driver Code let s1 = "AAB"; let s2 = "AAC"; let s3 = "AAAABC"; console.log(isInterleave(s1, s2, s3) ? "true" : "false");

Output
true

[Better Approach 2] Using Bottom-Up DP - O(m*n) Time and O(m*n) Space

Step by Step implementation:

  • The main idea is to create a 2D DP table dp[m+1][n+1] , where dp[i][j] represents whether s3[0...i+j-1] is an interleaving of s1[0...i-1] and s2[0...j-1].
  • dp[0][0] = true, because an empty s1 and s2 can form an empty s3.
  • Fill the First Row and First Column
    • If s1 is empty, we can only form s3 by taking characters from s2.
    • If s2 is empty, we can only form s3 by taking characters from s1.
  • The DP formula checks whether s3[k] (where k = i + j) matches either:
    • The current character of s1 (s1[i-1]), while ensuring that the previous part dp[i-1][j] is true.
    • The current character of s2 (s2[j-1]), while ensuring that the previous part dp[i][j-1] is true.
  • The DP table is filled iteratively until dp[m][n] contains the answer.
C++ 
// C++ program to check if Check if a String is Interleaving // of Other Two using Dynamic Programming #include <bits/stdc++.h> using namespace std; // The main function that // returns true if s3 is // an interleaving of s1 // and s2, otherwise false. bool isInterleave(string &s1, string &s2, string &s3) {  int m = s1.size(), n = s2.size();  // s3 can be an interleaving of s1 and s2 only if  // the sum of lengths of s1 & s2 is equal to the length of s3.  if (m + n != s3.size())  return false;  vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));  // Handle the corner case where both s1 and s2 are empty  dp[0][0] = true;  // Fill the first row (when s1 is empty)  for (int j = 1; j <= n; ++j)  {  dp[0][j] = (s2[j - 1] == s3[j - 1]) && dp[0][j - 1];  }  // Fill the first column (when s2 is empty)  for (int i = 1; i <= m; ++i)  {  dp[i][0] = (s1[i - 1] == s3[i - 1]) && dp[i - 1][0];  }  // Process all characters of s1 and s2  for (int i = 1; i <= m; ++i)  {  for (int j = 1; j <= n; ++j)  {  int k = i + j;  dp[i][j] = (s1[i - 1] == s3[k - 1] && dp[i - 1][j]) || (s2[j - 1] == s3[k - 1] && dp[i][j - 1]);  }  }  return dp[m][n]; } int main() {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  cout << (isInterleave(s1, s2, s3) ? "true" : "false") << endl;  return 0; }
Java 
// Java program to check if a String is Interleaving // of Other Two using Dynamic Programming import java.util.Arrays; class GfG {  // The main function that  // returns true if s3 is  // an interleaving of s1  // and s2, otherwise false.  static boolean isInterleave(String s1, String s2,  String s3)  {  int m = s1.length();  int n = s2.length();  // s3 can be an interleaving of s1 and s2 only if  // the sum of lengths of s1 & s2 is equal to the  // length of s3.  if (m + n != s3.length())  return false;  boolean[][] dp = new boolean[m + 1][n + 1];  // Handle the corner case where both s1 and s2 are  // empty  dp[0][0] = true;  // Fill the first row (when s1 is empty)  for (int j = 1; j <= n; ++j) {  dp[0][j]  = (s2.charAt(j - 1) == s3.charAt(j - 1))  && dp[0][j - 1];  }  // Fill the first column (when s2 is empty)  for (int i = 1; i <= m; ++i) {  dp[i][0]  = (s1.charAt(i - 1) == s3.charAt(i - 1))  && dp[i - 1][0];  }  // Process all characters of s1 and s2  for (int i = 1; i <= m; ++i) {  for (int j = 1; j <= n; ++j) {  int k = i + j;  dp[i][j]  = (s1.charAt(i - 1) == s3.charAt(k - 1)  && dp[i - 1][j])  || (s2.charAt(j - 1)  == s3.charAt(k - 1)  && dp[i][j - 1]);  }  }  return dp[m][n];  }  public static void main(String[] args)  {  String s1 = "AAB";  String s2 = "AAC";  String s3 = "AAAABC";  System.out.println(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
Python 
# Python program to check if a String is Interleaving # of Other Two using Dynamic Programming def isInterleave(s1, s2, s3): # The main function that # returns true if s3 is # an interleaving of s1 # and s2, otherwise false. m = len(s1) n = len(s2) # s3 can be an interleaving of s1 and s2 only if # the sum of lengths of s1 & s2 is equal to the length of s3. if m + n != len(s3): return False dp = [[False] * (n + 1) for _ in range(m + 1)] # Handle the corner case where both s1 and s2 are empty dp[0][0] = True # Fill the first row (when s1 is empty) for j in range(1, n + 1): dp[0][j] = (s2[j - 1] == s3[j - 1]) and dp[0][j - 1] # Fill the first column (when s2 is empty) for i in range(1, m + 1): dp[i][0] = (s1[i - 1] == s3[i - 1]) and dp[i - 1][0] # Process all characters of s1 and s2 for i in range(1, m + 1): for j in range(1, n + 1): k = i + j dp[i][j] = (s1[i - 1] == s3[k - 1] and dp[i - 1][j]) or \ (s2[j - 1] == s3[k - 1] and dp[i][j - 1]) return dp[m][n] if __name__ == "__main__": s1 = "AAB" s2 = "AAC" s3 = "AAAABC" print("true" if isInterleave(s1, s2, s3) else "false")
C# 
// C# program to check if a String is Interleaving // of Other Two using Dynamic Programming using System; class GfG {  // The main function that  // returns true if s3 is  // an interleaving of s1  // and s2, otherwise false.  static bool isInterleave(string s1, string s2,  string s3)  {  int m = s1.Length;  int n = s2.Length;  // s3 can be an interleaving of s1 and s2 only if  // the sum of lengths of s1 & s2 is equal to the  // length of s3.  if (m + n != s3.Length)  return false;  bool[, ] dp = new bool[m + 1, n + 1];  // Handle the corner case where both s1 and s2 are  // empty  dp[0, 0] = true;  // Fill the first row (when s1 is empty)  for (int j = 1; j <= n; ++j) {  dp[0, j]  = (s2[j - 1] == s3[j - 1]) && dp[0, j - 1];  }  // Fill the first column (when s2 is empty)  for (int i = 1; i <= m; ++i) {  dp[i, 0]  = (s1[i - 1] == s3[i - 1]) && dp[i - 1, 0];  }  // Process all characters of s1 and s2  for (int i = 1; i <= m; ++i) {  for (int j = 1; j <= n; ++j) {  int k = i + j;  dp[i, j] = (s1[i - 1] == s3[k - 1]  && dp[i - 1, j])  || (s2[j - 1] == s3[k - 1]  && dp[i, j - 1]);  }  }  return dp[m, n];  }  static void Main(string[] args)  {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  Console.WriteLine(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
JavaScript 
// JavaScript program to check if a String is Interleaving // of Other Two using Dynamic Programming function isInterleave(s1, s2, s3) {  // The main function that  // returns true if s3 is  // an interleaving of s1  // and s2, otherwise false.  let m = s1.length;  let n = s2.length;  // s3 can be an interleaving of s1 and s2 only if  // the sum of lengths of s1 & s2 is equal to the length  // of s3.  if (m + n !== s3.length)  return false;  let dp = Array(m + 1).fill(null).map(  () => Array(n + 1).fill(false));  // Handle the corner case where both s1 and s2 are empty  dp[0][0] = true;  // Fill the first row (when s1 is empty)  for (let j = 1; j <= n; ++j) {  dp[0][j]  = (s2[j - 1] === s3[j - 1]) && dp[0][j - 1];  }  // Fill the first column (when s2 is empty)  for (let i = 1; i <= m; ++i) {  dp[i][0]  = (s1[i - 1] === s3[i - 1]) && dp[i - 1][0];  }  // Process all characters of s1 and s2  for (let i = 1; i <= m; ++i) {  for (let j = 1; j <= n; ++j) {  let k = i + j;  dp[i][j]  = (s1[i - 1] === s3[k - 1] && dp[i - 1][j])  || (s2[j - 1] === s3[k - 1]  && dp[i][j - 1]);  }  }  return dp[m][n]; } // Driver Code let s1 = "AAB"; let s2 = "AAC"; let s3 = "AAAABC"; console.log(isInterleave(s1, s2, s3) ? "true" : "false");

Output
true

[Expected Approach] Space-Optimized DP - O(n * m) Time and O(m) Space

The idea is to optimize DP space by using two 1D arrays instead of a 2D table.

We check if s3 can be formed by interleaving s1 and s2 while maintaining relative order. prev stores results of the previous row, while cur stores the current row values.

We fill the first row for cases where s1 is empty, then iterate through both strings, updating cur[j] based on matches with s3. After processing a row, prev is updated with cur, ensuring space efficiency.

Steps to implement the above idea:

  • Check if the total length matches, return false if not.
  • Initialize two arrays prev and cur to store previous and current results.
  • Set the base case where an empty prefix is valid.
  • Fill the first row based on matches with s2.
  • Iterate through both s1 and s2, updating cur based on matches.
  • Return cur[m], indicating interleaving validity.


C++ 
// CPP program to check if a string is // interleaving of other two strings #include <bits/stdc++.h> using namespace std; bool isInterleave(string &s1, string &s2, string &s3) {  // return false is length of s3 is  // not equal to sum of lengths of s1 and s2  if (s1.size() + s2.size() != s3.size())  return false;  int n = s1.size(), m = s2.size();  // Create two arrays prev and cur to store  // results of previous and current states  vector<int> prev(m + 1), cur(m + 1);  // set empty strings as true  prev[0] = true;  // Fill the first row (when s1 is empty)  for (int j = 1; j <= m; ++j)  {  prev[j] = (s2[j - 1] == s3[j - 1]) && prev[j - 1];  }  // Process all characters of s1 and s2  for (int i = 1; i <= n; ++i)  {  // fill the first column of current row  cur[0] = (s1[i - 1] == s3[i - 1]) && prev[0];  for (int j = 1; j <= m; ++j)  {  int k = i + j;  cur[j] = (s1[i - 1] == s3[k - 1] && prev[j]) || (s2[j - 1] == s3[k - 1] && cur[j - 1]);  }  // store current row in previous row  prev = cur;  }  return cur[m]; } int main() {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  cout << (isInterleave(s1, s2, s3) ? "true" : "false");  return 0; }
Java 
// Java program to check if a string is // interleaving of other two strings import java.util.*; class GfG {  static boolean isInterleave(String s1, String s2,  String s3)  {  // return false if length of s3 is  // not equal to sum of lengths of s1 and s2  if (s1.length() + s2.length() != s3.length())  return false;  int n = s1.length(), m = s2.length();  // Create two arrays prev and cur to store  // results of previous and current states  int[] prev = new int[m + 1];  int[] cur = new int[m + 1];  // set empty strings as true  prev[0] = 1;  // Fill the first row (when s1 is empty)  for (int j = 1; j <= m; ++j) {  prev[j] = (s2.charAt(j - 1) == s3.charAt(j - 1))  && (prev[j - 1] == 1)  ? 1  : 0;  }  // Process all characters of s1 and s2  for (int i = 1; i <= n; ++i) {  // fill the first column of current row  cur[0] = (s1.charAt(i - 1) == s3.charAt(i - 1))  && (prev[0] == 1)  ? 1  : 0;  for (int j = 1; j <= m; ++j) {  int k = i + j;  cur[j]  = ((s1.charAt(i - 1) == s3.charAt(k - 1)  && prev[j] == 1)  || (s2.charAt(j - 1)  == s3.charAt(k - 1)  && cur[j - 1] == 1))  ? 1  : 0;  }  // store current row in previous row  prev = Arrays.copyOf(cur, m + 1);  }  return cur[m] == 1;  }  public static void main(String[] args)  {  String s1 = "AAB";  String s2 = "AAC";  String s3 = "AAAABC";  System.out.println(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
Python 
# Python program to check if a string is # interleaving of other two strings def isInterleave(s1, s2, s3): # return false if length of s3 is # not equal to sum of lengths of s1 and s2 if len(s1) + len(s2) != len(s3): return False n, m = len(s1), len(s2) # Create two arrays prev and cur to store # results of previous and current states prev = [0] * (m + 1) cur = [0] * (m + 1) # set empty strings as true prev[0] = 1 # Fill the first row (when s1 is empty) for j in range(1, m + 1): prev[j] = int(s2[j - 1] == s3[j - 1] and prev[j - 1]) # Process all characters of s1 and s2 for i in range(1, n + 1): # fill the first column of current row cur[0] = int(s1[i - 1] == s3[i - 1] and prev[0]) for j in range(1, m + 1): k = i + j cur[j] = int((s1[i - 1] == s3[k - 1] and prev[j]) or (s2[j - 1] == s3[k - 1] and cur[j - 1])) # store current row in previous row prev = cur[:] return cur[m] == 1 if __name__ == "__main__": s1 = "AAB" s2 = "AAC" s3 = "AAAABC" print("true" if isInterleave(s1, s2, s3) else "false")
C# 
// C# program to check if a string is // interleaving of other two strings using System; class GfG {  static bool isInterleave(string s1, string s2,  string s3)  {  // return false if length of s3 is  // not equal to sum of lengths of s1 and s2  if (s1.Length + s2.Length != s3.Length)  return false;  int n = s1.Length, m = s2.Length;  // Create two arrays prev and cur to store  // results of previous and current states  int[] prev = new int[m + 1];  int[] cur = new int[m + 1];  // set empty strings as true  prev[0] = 1;  // Fill the first row (when s1 is empty)  for (int j = 1; j <= m; ++j) {  prev[j] = (s2[j - 1] == s3[j - 1]  && prev[j - 1] == 1)  ? 1  : 0;  }  // Process all characters of s1 and s2  for (int i = 1; i <= n; ++i) {  // fill the first column of current row  cur[0]  = (s1[i - 1] == s3[i - 1] && prev[0] == 1)  ? 1  : 0;  for (int j = 1; j <= m; ++j) {  int k = i + j;  cur[j] = ((s1[i - 1] == s3[k - 1]  && prev[j] == 1)  || (s2[j - 1] == s3[k - 1]  && cur[j - 1] == 1))  ? 1  : 0;  }  // store current row in previous row  Array.Copy(cur, prev, m + 1);  }  return cur[m] == 1;  }  static void Main()  {  string s1 = "AAB";  string s2 = "AAC";  string s3 = "AAAABC";  Console.WriteLine(  isInterleave(s1, s2, s3) ? "true" : "false");  } }
JavaScript 
// JavaScript program to check if a string is // interleaving of other two strings function isInterleave(s1, s2, s3) {  // return false if length of s3 is  // not equal to sum of lengths of s1 and s2  if (s1.length + s2.length !== s3.length)  return false;  const n = s1.length, m = s2.length;  // Create two arrays prev and cur to store  // results of previous and current states  const prev = Array(m + 1).fill(0);  const cur = Array(m + 1).fill(0);  // set empty strings as true  prev[0] = 1;  // Fill the first row (when s1 is empty)  for (let j = 1; j <= m; ++j) {  prev[j] = (s2[j - 1] === s3[j - 1] && prev[j - 1])  ? 1  : 0;  }  // Process all characters of s1 and s2  for (let i = 1; i <= n; ++i) {  // fill the first column of current row  cur[0]  = (s1[i - 1] === s3[i - 1] && prev[0]) ? 1 : 0;  for (let j = 1; j <= m; ++j) {  const k = i + j;  cur[j] = ((s1[i - 1] === s3[k - 1] && prev[j])  || (s2[j - 1] === s3[k - 1]  && cur[j - 1]))  ? 1  : 0;  }  // store current row in previous row  prev.splice(0, m + 1, ...cur);  }  return !!cur[m]; } // Driver Code const s1 = "AAB"; const s2 = "AAC"; const s3 = "AAAABC"; console.log(isInterleave(s1, s2, s3) ? "true" : "false");

Output
true

K
kartik
Article Tags :

Explore

Lightbox