Check if a string is interleaving of two other given strings
Given three strings, return true if the third string is interleaving the first and second strings, i.e., it is formed from all characters of the first and second string, and the order of characters is preserved.
For example,
ACDB is interleaving of AB and CD
ADEBCF is interleaving of ABC and DEF
ACBCD is interleaving of ABC and CD
ACDABC is interleaving of ABC and ACD
ADEBCF is interleaving of ABC and DEF
ACBCD is interleaving of ABC and CD
ACDABC is interleaving of ABC and ACD
We can easily solve this problem by using recursion, as demonstrated below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> using namespace std; // Function to check if strings 'X' and 'Y' are interleaving of string 'S' or not bool isInterleaving(string X, string Y, string S) { // return true if the end of all strings is reached if (!X.length() && !Y.length() && !S.length()) { return true; } // return false if the end of string 'S' is reached, // but string 'X' or 'Y' is not empty if (!S.length()) { return false; } // if string 'X' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring if (X.length() && S[0] == X[0]) { return isInterleaving(X.substr(1), Y, S.substr(1)); } // if string 'Y' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring if (Y.length() && S[0] == Y[0]) { return isInterleaving(X, Y.substr(1), S.substr(1)); } return false; } int main() { string X = "ABC"; string Y = "DEF"; string S = "ADEBCF"; if (isInterleaving(X, Y, S)) { cout << "Interleaving"; } else { cout << "Not an Interleaving"; } return 0; } |
Output:
Interleaving
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Main { // Function to check if strings 'X' and 'Y' are interleaving of string 'S' or not public static boolean isInterleaving(String X, String Y, String S) { // return true if the end of all strings is reached if (X.length() == 0 && Y.length() == 0 && S.length() == 0) { return true; } // return false if the end of string 'S' is reached, // but string 'X' or 'Y' is not empty if (S.length() == 0) { return false; } // if string 'X' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring if (X.length() != 0 && S.charAt(0) == X.charAt(0)) { return isInterleaving(X.substring(1), Y, S.substring(1)); } // if string 'Y' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring if (Y.length() != 0 && S.charAt(0) == Y.charAt(0)) { return isInterleaving(X, Y.substring(1), S.substring(1)); } return false; } public static void main(String[] args) { String X = "ABC"; String Y = "DEF"; String S = "ADEBFC"; if (isInterleaving(X, Y, S)) { System.out.print("Interleaving"); } else { System.out.print("Given string is not interleaving of X and Y"); } } } |
Output:
Interleaving
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
# Function to check if strings 'X' and 'Y' are interleaving of 'S' or not def isInterleaving(X, Y, S): # return true if the end of all strings is reached if not X and not Y and not S: return True # return false if the end of string 'S' is reached, # but 'X' or 'Y' is not empty if not S: return False # if string 'X' is not empty and its first character matches with the # first character of 'S', recur for the remaining substring if X and S[0] == X[0]: return isInterleaving(X[1:], Y, S[1:]) # if string 'Y' is not empty and its first character matches with the # first character of 'S', recur for the remaining substring if Y and S[0] == Y[0]: return isInterleaving(X, Y[1:], S[1:]) return False if __name__ == '__main__': X = 'ABC' Y = 'DEF' S = 'ADEBFC' if isInterleaving(X, Y, S): print('Interleaving') else: print('Not an Interleaving') |
Output:
Interleaving
The time complexity of the above solution is O(m + n), where m and n are the length of the string X and Y. The auxiliary space required by the program is O(1).
The problem with the above solution is that it doesn’t handle duplicates. Suppose X = "ABC" and Y = "ACD", then the above solution will return false for string S = "ACDABC". The reason is that if the current character of S matches the current character of both X and Y, the solution will always pair S with X and do not check if the solution can be formed by pairing S with Y or not.
We can easily handle duplicates by pairing S with both X and Y and recursively check if the solution can be formed by either of them or not. Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <iostream> using namespace std; // Function to check if strings 'X' and 'Y' are interleaving of string 'S' or not bool isInterleaving(string X, string Y, string S) { // return true if the end of all strings is reached if (!X.length() && !Y.length() && !S.length()) { return true; } // return false if the end of string 'S' is reached, // but string 'X' or 'Y' is not empty if (!S.length()) { return false; } // if string 'X' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring bool x = (X.length() && S[0] == X[0]) && isInterleaving(X.substr(1), Y, S.substr(1)); // if string 'Y' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring bool y = (Y.length() && S[0] == Y[0]) && isInterleaving(X, Y.substr(1), S.substr(1)); return x || y; } int main() { string X = "ABC"; string Y = "ACD"; string S = "ACDABC"; if (isInterleaving(X, Y, S)) { cout << "Interleaving"; } else { cout << "Not an Interleaving"; } return 0; } |
Output:
Interleaving
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Main { // Function to check if strings 'X' and 'Y' are interleaving of string 'S' or not public static boolean isInterleaving(String X, String Y, String S) { // return true if the end of all strings is reached if (X.length() == 0 && Y.length() == 0 && S.length() == 0) { return true; } // return false if the end of string 'S' is reached, // but string 'X' or 'Y' is not empty if (S.length() == 0) { return false; } // if string 'X' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring boolean x = (X.length() != 0 && S.charAt(0) == X.charAt(0)) && isInterleaving(X.substring(1), Y, S.substring(1)); // if string 'Y' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring boolean y = (Y.length() != 0 && S.charAt(0) == Y.charAt(0)) && isInterleaving(X, Y.substring(1), S.substring(1)); return x || y; } public static void main(String[] args) { String X = "ABC"; String Y = "DEF"; String S = "ADEBFC"; if (isInterleaving(X, Y, S)) { System.out.print("Interleaving"); } else { System.out.print("Given string is not interleaving of X and Y"); } } } |
Output:
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
# Function to check if strings 'X' and 'Y' are interleaving of 'S' or not def isInterleaving(X, Y, S): # return true if the end of all strings is reached if not X and not Y and not S: return True # return false if the end of string 'S' is reached, # but 'X' or 'Y' is not empty if not S: return False # if string 'X' is not empty and its first character matches with the # first character of 'S', recur for the remaining substring x = (len(X) and S[0] == X[0]) and isInterleaving(X[1:], Y, S[1:]) # if string 'Y' is not empty and its first character matches with the # first character of 'S', recur for the remaining substring y = (len(Y) and S[0] == Y[0]) and isInterleaving(X, Y[1:], S[1:]) return x or y if __name__ == '__main__': X = 'ABC' Y = 'DEF' S = 'ADEBFC' if isInterleaving(X, Y, S): print('Interleaving') else: print('Not an Interleaving') |
Output:
Interleaving
The worst-case time complexity of the above solution is exponential and occupies space in the call stack. The worst case happens when all characters of X and Y are the same. We can use dynamic programming to reduce the worst-case time complexity and space complexity to O(m.n).
The DP solution is discussed below in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <unordered_map> using namespace std; // Function to check if strings 'X' and 'Y' are interleaving of string 'S' or not bool isInterleaving(string X, string Y, string S, auto &T) { // return true if the end of all strings is reached if (!X.length() && !Y.length() && !S.length()) { return true; } // return false if the end of string 'S' is reached, // but string 'X' or 'Y' is not empty if (!S.length()) { return false; } // calculate a unique map key by using delimiter `|` string key = (X + "|" + Y + "|" + S); // if the subproblem is seen for the first time if (T.find(key) == T.end()) { // if string 'X' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring bool x = (X.length() && S[0] == X[0]) && isInterleaving(X.substr(1), Y, S.substr(1), T); // if string 'Y' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring bool y = (Y.length() && S[0] == Y[0]) && isInterleaving(X, Y.substr(1), S.substr(1), T); T[key] = x || y; } return T[key]; } int main() { string X = "ABC"; string Y = "ACD"; string S = "ACDABC"; // map to store solution to already computed subproblems unordered_map<string, bool> T; if (isInterleaving(X, Y, S, T)) { cout << "Interleaving"; } else { cout << "Not an Interleaving"; } return 0; } |
Output:
Interleaving
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.HashMap; import java.util.Map; class Main { // Function to check if strings 'X' and 'Y' are interleaving of string 'S' or not public static boolean isInterleaving(String X, String Y, String S, Map<String, Boolean> T) { // return true if the end of all strings is reached if (X.length() == 0 && Y.length() == 0 && S.length() == 0) { return true; } // return false if the end of string 'S' is reached, // but string 'X' or 'Y' is not empty if (S.length() == 0) { return false; } // calculate a unique map key by using delimiter `|` String key = (X + "|" + Y + "|" + S); // if the subproblem is seen for the first time if (!T.containsKey(key)) { // if string 'X' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring boolean x = (X.length() != 0 && S.charAt(0) == X.charAt(0)) && isInterleaving(X.substring(1), Y, S.substring(1), T); // if string 'Y' is not empty and its first character matches with the // first character of 'S', recur for the remaining substring boolean y = (Y.length() != 0 && S.charAt(0) == Y.charAt(0)) && isInterleaving(X, Y.substring(1), S.substring(1), T); T.put(key, x || y); } return T.get(key); } public static void main(String[] args) { String X = "ABC"; String Y = "ACD"; String S = "ACDABC"; // map to store solution to already computed subproblems Map<String, Boolean> T = new HashMap<>(); if (isInterleaving(X, Y, S, T)) { System.out.print("Interleaving"); } else { System.out.print("Given string is not interleaving of X and Y"); } } } |
Output:
Interleaving
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
# Function to check if strings 'X' and 'Y' are interleaving of 'S' or not def isInterleaving(X, Y, S, T): # return true if the end of all strings is reached if not X and not Y and not S: return True # return false if the end of string 'S' is reached, # but 'X' or 'Y' is not empty if not S: return False # calculate a unique key by using delimiter `|` key = (X, Y, S) # if the subproblem is seen for the first time if key not in T: # if string 'X' is not empty and its first character matches with the # first character of 'S', recur for the remaining substring x = (len(X) and S[0] == X[0]) and isInterleaving(X[1:], Y, S[1:], T) # if string 'Y' is not empty and its first character matches with the # first character of 'S', recur for the remaining substring y = (len(Y) and S[0] == Y[0]) and isInterleaving(X, Y[1:], S[1:], T) T[key] = x or y return T[key] if __name__ == '__main__': X = 'ABC' Y = 'ACD' S = 'ACDABC' # dictionary to store solution to already computed subproblems T = {} if isInterleaving(X, Y, S, T): print('Interleaving') else: print('Not an Interleaving') |
Output:
Interleaving
We can even write a bottom-up version of the above memoized solution. The following code shows how to implement it in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <iostream> using namespace std; // Function to check if strings 'X' and 'Y' are interleaving of 'S' or not bool isInterleaving(string X, string Y, string S) { int M = X.size(); int N = Y.size(); // base case: the size of a given string doesn't match // the sum of sizes of input strings if (M + N != S.size()) { return false; } // Create a lookup table T[][] to store solution to already computed // subproblems. T[i][j] is true when `S[0…i+j-1]` is an interleaving // of `X[0…i-1]` and `Y[0…j-1]` bool T[M + 1][N + 1]; // fill the lookup table in a bottom-up manner for (int i = 0; i <= M; i++) { for (int j = 0; j <= N; j++) { if (i == 0 && j == 0) { // both strings are empty T[i][j] = true; } // if the current char of 'S' matches the current char of both 'A' and 'B' else if (i and j and X[i - 1] == S[i + j - 1] and Y[j - 1] == S[i + j - 1]) { T[i][j] = T[i - 1][j] || T[i][j - 1]; } // if the current char of 'X' matches with the current char of 'S' else if (i and X[i - 1] == S[i + j - 1]) { T[i][j] = T[i - 1][j]; } // if the current char of 'Y' matches with the current char of 'S' else if (j and Y[j - 1] == S[i + j - 1]) { T[i][j] = T[i][j - 1]; } } } // T[M][N] stores the result return T[M][N]; } int main() { string X = "ABC"; string Y = "ACD"; string S = "ACDABC"; if (isInterleaving(X, Y, S)) { cout << "Interleaving"; } else { cout << "Not an Interleaving"; } return 0; } |
Output:
Interleaving
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
class Main { // Function to check if strings 'X' and 'Y' are interleaving of 'S' or not public static boolean isInterleaving(String X, String Y, String S) { int M = X.length(); int N = Y.length(); // base case: length of given strings doesn't match if (M + N != S.length()) { return false; } // create a lookup table T[][] to store solutions to already computed // subproblems. T[i][j] will be true when `S[0…i+j-1]` is an // interleaving of `X[0…i-1]` and `Y[0…j-1]` boolean[][] T = new boolean[M + 1][N + 1]; // fill the lookup table in a bottom-up manner for (int i = 0; i <= M; i++) { for (int j = 0; j <= N; j++) { if (i == 0 && j == 0) { // both strings are empty T[i][j] = true; } // if the current char of 'S' matches the current char of both // 'A' and 'B' else if (i != 0 && j != 0 && X.charAt(i - 1) == S.charAt(i + j - 1) && Y.charAt(j - 1) == S.charAt(i + j - 1)) { T[i][j] = T[i - 1][j] || T[i][j - 1]; } // if the current char of 'X' matches with the current char of 'S' else if (i != 0 && X.charAt(i - 1) == S.charAt(i + j - 1)) { T[i][j] = T[i - 1][j]; } // if the current char of 'Y' matches with the current char of 'S' else if (j !=0 && Y.charAt(j - 1) == S.charAt(i + j - 1)) { T[i][j] = T[i][j - 1]; } } } // T[M][N] stores the result return T[M][N]; } public static void main(String[] args) { String X = "ABC"; String Y = "ACD"; String S = "ACDABC"; if (isInterleaving(X, Y, S)) { System.out.println("Interleaving"); } else { System.out.println("Not an Interleaving"); } } } |
Output:
Interleaving
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# Function to check if strings 'X' and 'Y' are interleaving of 'S' or not def isInterleaving(X, Y, S): M, N = len(X), len(Y) # base case: length of given strings doesn't match if M + N != len(S): return False # Create a lookup table T[][] to store solution to already computed # subproblems. T[i][j] is true when `S[0…i+j-1]` is an interleaving # of `X[0…i-1]` and `Y[0…j-1]` T = [[False for x in range(N + 1)] for y in range(M + 1)] # fill the lookup table in a bottom-up manner for i in range(0, M + 1): for j in range(0, N + 1): if i == 0 and j == 0: # both strings are empty T[i][j] = True # if the current char of 'S' matches the current char of both 'A' and 'B' elif i and j and X[i - 1] == S[i + j - 1] and Y[j - 1] == S[i + j - 1]: T[i][j] = T[i - 1][j] or T[i][j - 1] # if the current char of 'X' matches with the current char of 'S' elif i and X[i - 1] == S[i + j - 1]: T[i][j] = T[i - 1][j] # if the current char of 'Y' matches with the current char of 'S' elif j and Y[j - 1] == S[i + j - 1]: T[i][j] = T[i][j - 1] # T[M][N] stores the result return T[M][N] if __name__ == '__main__': X = 'ABC' Y = 'ACD' S = 'ACDABC' if isInterleaving(X, Y, S): print('Interleaving') else: print('Not an Interleaving') |
Output:
Interleaving
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)