Interleaving String
Given three strings: s1, s2, and s3. Determine if s3 is an interleaving of s1 and s2. An interleaving of two strings s and t is a string containing all characters of both s and t, and the order of characters in the interleaved string should be the same as the order of characters in the original strings.
Constraints:
- 0 <= s1.length, s2.length <= 100
- 0 <= s3.length <= 200
- s1, s2, and s3 consist of lowercase English letters.
Examples:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: s3 is an interleaving of s1 and s2 because it contains all characters of both s1 and s2, and the order of characters in the interleaved string is the same as the order of characters in the original strings.
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: s3 is not an interleaving of s1 and s2 because it does not contain all characters of both s1 and s2 in the correct order.
Input: s1 = "", s2 = "", s3 = ""
Output: true
Explanation: An empty string is an interleaving of two empty strings.
Solutions
Dynamic Programming
The dynamic programming approach works by creating a 2D table dp where dp[i][j] is true if the first i characters of s1 and the first j characters of s2 can be interleaved to form the first i + j characters of s3. The base cases are when i or j is 0, in which case we only need to check if the corresponding substring of s1 or s2 matches the substring of s3. For the recursive case, we check if the current character of s1 or s2 matches the current character of s3, and if the previous characters can be interleaved.
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (m + n != s3.length()) return false;
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 1;
i <= m;
i++) dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
for (int j = 1;
j <= n;
j++) dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
for (int i = 1;
i <= m;
i++) for (int j = 1;
j <= n;
j++) 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[m][n];
}Follow-up:
What if the strings are very large and we need to optimize the space complexity?
