Dynamic Programming | Set 33 (Find if a string is interleaved of two other strings) - GeeksforGeeks
Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. 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.
We have discussed a simple solution of this problem here. The simple solution doesn’t work if strings A and B have some common characters. For example A = “XXY”, string B = “XXZ” and string C = “XXZXXXY”. To handle all cases, two possibilities need to be considered.
a) If first character of C matches with first character of A, we move one character ahead in A and C and recursively check.
b) If first character of C matches with first character of B, we move one character ahead in B and C and recursively check.
If any of the above two cases is true, we return true, else false.
Auxiliary Space: O(MN)
Read full article from Dynamic Programming | Set 33 (Find if a string is interleaved of two other strings) - GeeksforGeeks
Given three strings A, B and C. Write a function that checks whether C is an interleaving of A and B. 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.
We have discussed a simple solution of this problem here. The simple solution doesn’t work if strings A and B have some common characters. For example A = “XXY”, string B = “XXZ” and string C = “XXZXXXY”. To handle all cases, two possibilities need to be considered.
a) If first character of C matches with first character of A, we move one character ahead in A and C and recursively check.
b) If first character of C matches with first character of B, we move one character ahead in B and C and recursively check.
If any of the above two cases is true, we return true, else false.
Dynamic Programming
Time Complexity: O(MN)Auxiliary Space: O(MN)
bool isInterleaved(char* A, char* B, char* C){ // Find lengths of the two strings int M = strlen(A), N = strlen(B); // Let us create a 2D table to store solutions of // subproblems. C[i][j] will be true if C[0..i+j-1] // is an interleaving of A[0..i-1] and B[0..j-1]. bool IL[M+1][N+1]; memset(IL, 0, sizeof(IL)); // Initialize all values as false. // C can be an interleaving of A and B only of sum // of lengths of A & B is equal to length of C. if ((M+N) != strlen(C)) return false; // Process all characters of A and B for (int i=0; i<=M; ++i) { for (int j=0; j<=N; ++j) { // two empty strings have an empty string // as interleaving if (i==0 && j==0) IL[i][j] = true; // A is empty else if (i==0 && B[j-1]==C[j-1]) IL[i][j] = IL[i][j-1]; // B is empty else if (j==0 && A[i-1]==C[i-1]) IL[i][j] = IL[i-1][j]; // Current character of C matches with current character of A, // but doesn't match with current character of B else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j-1]) IL[i][j] = IL[i-1][j]; // Current character of C matches with current character of B, // but doesn't match with current character of A else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1]) IL[i][j] = IL[i][j-1]; // Current character of C matches with that of both A and B else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1]) IL[i][j]=(IL[i-1][j] || IL[i][j-1]) ; } } return IL[M][N];}Test if s is an interleaving of s_1 and $s_2$ InterleavingString.java
public static boolean isInterleavingString(String s1, String s2, String s3) {
// Early return if |s1| + |s2| != |s3|.
if (s1.length() + s2.length() != s3.length()) {
return false;
}
boolean[][] T = new boolean[s1.length() + 1][s2.length() + 1];
T[0][0] = true; // Base case.
// Uses chars from s1 only to match s3.
for (int i = 0; i < s1.length(); ++i) {
if (s1.charAt(i) == s3.charAt(i)) {
T[i + 1][0] = true;
} else {
break;
}
}
// Uses chars from s2 only to match s3.
for (int j = 0; j < s2.length(); ++j) {
if (s2.charAt(j) == s3.charAt(j)) {
T[0][j + 1] = true;
} else {
break;
}
}
for (int i = 0; i < s1.length(); ++i) {
for (int j = 0; j < s2.length(); ++j) {
T[i + 1][j + 1] = (T[i][j + 1] && s1.charAt(i) == s3.charAt(i + j + 1))
|| (T[i + 1][j] && s2.charAt(j) == s3.charAt(i + j + 1));
}
}
return T[s1.length()][s2.length()];
}
// A simple recursive function to check whether C is an interleaving of A and Bbool isInterleaved(char *A, char *B, char *C){ // Base Case: If all strings are empty if (!(*A || *B || *C)) return true; // If C is empty and any of the two strings is not empty if (*C == '\0') return false; // If any of the above mentioned two possibilities is true, // then return true, otherwise false return ( (*C == *A) && isInterleaved(A+1, B, C+1)) || ((*C == *B) && isInterleaved(A, B+1, C+1));}Read full article from Dynamic Programming | Set 33 (Find if a string is interleaved of two other strings) - GeeksforGeeks
