Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc"
,
s2 = "dbbca"
,
When s3 = "aadbbcbcac"
, return true.
When s3 = "aadbbbaccc"
, return false.
We need to determine whether a given string can be formed by interleaving the other two strings.
The most basic idea is to find every string possible by all interleavings of the two given strings( and ). In order to implement this method, we are using recursion. We start by taking the current character of the first string() and then appending all possible interleavings of the remaining portion of the first string() and the second string() and comparing each result formed with the required interleaved string(). Similarly, we choose one character from the second string() and form all the interleavings with the remaining portion of and to check if the required string can be formed.
For implementing the recursive function, we make the function call recursively as in which we have chosen the current character from and then make another function call , in which the current character of is chosen. Here, refers to that portion(interleaved) of and which has already been processed. If anyone of these calls return the result as , it means that atleast one interleaving gives the required result . The recursive calls end when both the strings and have been fully processed.
Let's look at a small example to see how the execution proceeds.
s1="abc" s2="bcd" s3="abcbdc"
Firstly we choose 'a' of s1 as the processed part i.e. res and call the recursive function considering the new strings as s1="bc", s2="bcd", s3="abcbdc". When this function returns a result, we again call the recursive function but with the new strings as s1="abc", s2="cd", s3="abcbdc"
Java
public class Solution { public boolean is_Interleave(String s1,int i,String s2,int j,String res,String s3) { if(res.equals(s3) && i==s1.length() && j==s2.length()) return true; boolean ans=false; if(i<s1.length()) ans|=is_Interleave(s1,i+1,s2,j,res+s1.charAt(i),s3); if(j<s2.length()) ans|=is_Interleave(s1,i,s2,j+1,res+s2.charAt(j),s3); return ans; } public boolean isInterleave(String s1, String s2, String s3) { return is_Interleave(s1,0,s2,0,"",s3); } }
Complexity Analysis
Time complexity : . is the length of and is the length of .
Space complexity : . The size of stack for recursive calls can go upto .
Algorithm
In the recursive approach discussed above, we are considering every possible string formed by interleaving the two given strings. But, there will be cases encountered in which, the same portion of and would have been processed already but in different orders(permutations). But irrespective of the order of processing, if the resultant string formed till now is matching with the required string(), the final result is dependent only on the remaining portions of and , but not on the already processed portion. Thus, the recursive approach leads to redundant computations.
This redundancy can be removed by making use of memoization along with recursion. For this, we maitain 3 pointers which correspond to the index of the current character of respectively. Also, we maintain a 2-d memo array to keep a track of the substrings processed so far. stores a 1/0 or -1 depending on whether the current portion of strings i.e. upto index for and upto index for s2 has already been evaluated. Again, we start by selecting the current character of (pointed by $$i$). If it matches the current character of (pointed by ), we include it in the processed string and call the same function recurively as:
Thus, here we have called the function by incrementing the pointers and since the portion of strings upto those indices has already been processed. Similarly, we choose one character from the second string and continue. The recursive function ends when either of the two strings or has been fully processed. If, let's say, the string has been fully processed, we directly compare the remaining portion of with the remaining portion of . When the backtrack occurs from the recursive calls, we store the value returned by the recursive functions in the memoization array memo appropriatelys so that when it is encountered the next time, the recursive function won't be called, but the memoization array itself will return the previous generated result.
Java
public class Solution { public boolean is_Interleave(String s1, int i, String s2, int j, String s3, int k, int[][] memo) { if (i == s1.length()) { return s2.substring(j).equals(s3.substring(k)); } if (j == s2.length()) { return s1.substring(i).equals(s3.substring(k)); } if (memo[i][j] >= 0) { return memo[i][j] == 1 ? true : false; } boolean ans = false; if (s3.charAt(k) == s1.charAt(i) && is_Interleave(s1, i + 1, s2, j, s3, k + 1, memo) || s3.charAt(k) == s2.charAt(j) && is_Interleave(s1, i, s2, j + 1, s3, k + 1, memo)) { ans = true; } memo[i][j] = ans ? 1 : 0; return ans; } public boolean isInterleave(String s1, String s2, String s3) { int memo[][] = new int[s1.length()][s2.length()]; for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); j++) { memo[i][j] = -1; } } return is_Interleave(s1, 0, s2, 0, s3, 0, memo); } }
Complexity Analysis
Time complexity : . is the length of and is the length of .
Space complexity : . The size of stack for recursive calls can go upto .
Algorithm
The recursive approach discussed in above solution included a character from one of the strings or in the resultant interleaved string and called a recursive function to check whether the remaining portions of and can be interleaved to form the remaining portion of . In the current approach, we look at the same problem the other way around. Here, we include one character from or and check whether the resultant string formed so far by one particular interleaving of the the current prefix of and form a prefix of .
Thus, this approach relies on the fact that the in order to determine whether a substring of (upto index ), can be formed by interleaving strings and upto indices and respectively, solely depends on the characters of and upto indices and only and not on the characters coming afterwards.
To implement this method, we'll make use of a 2-d boolean array . In this array implies if it is possible to obtain a substring of length which is a prefix of by some interleaving of prefixes of strings and having lengths and respectively. For filling in the entry of , we need to consider two cases:
The character just included i.e. either at index of or at index of doesn't match the character at index of , where . In this case, the resultant string formed using some interleaving of prefixes of and can never result in a prefix of length in . Thus, we enter at the character .
The character just included i.e. either at index of or at index of matches the character at index of , where . Now, if the character just included(say ) which matches the character at index of , is the character at index of , we need to keep at the last position in the resultant interleaved string formed so far. Thus, in order to use string and upto indices and to form a resultant string of length which is a prefix of , we need to ensure that the strings and upto indices and respectively obey the same property.
Similarly, if we just included the character of , which matches with the character of , we need to ensure that the strings and upto indices and also obey the same property to enter a at .
This can be made clear with the following example:
s1="aabcc" s2="dbbca" s3="aadbbcbcac"
!?!../Documents/97_Interleaving.json:1000,563!?!
Java
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if (s3.length() != s1.length() + s2.length()) { return false; } boolean dp[][] = new boolean[s1.length() + 1][s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { for (int j = 0; j <= s2.length(); j++) { if (i == 0 && j == 0) { dp[i][j] = true; } else if (i == 0) { dp[i][j] = dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1); } else if (j == 0) { dp[i][j] = dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1); } else { dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)); } } } return dp[s1.length()][s2.length()]; } }
Complexity Analysis
Time complexity : . dp array of size is filled.
Space complexity : . 2-d DP of size is required. and are the lengths of strings and repectively.
Algorithm
This approach is the same as the previous approach except that we have used only 1-d array to store the results of the prefixes of the strings processed so far. Instead of maintaining a 2-d array, we can maintain a 1-d array only and update the array's element when needed using and the previous value of .
Java
public class Solution { public boolean isInterleave(String s1, String s2, String s3) { if (s3.length() != s1.length() + s2.length()) { return false; } boolean dp[] = new boolean[s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { for (int j = 0; j <= s2.length(); 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[s2.length()]; } }
Complexity Analysis
Time complexity : . dp array of size is filled times.
Space complexity : . is the length of the string .
Analysis written by: @vinod23