Problem
Given stringss1, s2, and s3, determine whether s3 can be formed by interleaving s1 and s2.
An interleaving must preserve the relative order of characters from both s1 and s2.
Example(s)
Consider the following example to understand the expected input and output.Input
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"Output
trueExplanation
s3 = "aa" + "dbbc" + "bc" + "a" + "c"
s1 and s2 are interleaved while preserving the original order of characters within each string.
Solution
This problem can be solved using Dynamic Programming with Memoization.First, the lengths of
s1 and s2 must add up to the length of s3. Otherwise, forming s3 is impossible. We use
i and j to represent the current positions in s1 and s2. The corresponding position in s3 is i + j, because we have already consumed i characters from s1 and j characters from s2. At each position, we have two possible choices. If the current character of
s1 matches the corresponding character of s3, we can take the character from s1. Similarly, if the current character of s2 matches, we can take the character from s2. If either choice can successfully reach the end of
s3, the strings can be interleaved. We store each (i, j) state in memo to avoid recalculating the same state.
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length())
return false;
Boolean[][] memo = new Boolean[s1.length() + 1][s2.length() + 1];
return isInterleaveHelper(s1, s2, s3, 0, 0, memo);
}
private boolean isInterleaveHelper(String s1, String s2, String s3, int i, int j, Boolean[][] memo) {
// All characters from s1 and s2 have been used
if (i == s1.length() && j == s2.length())
return true;
// Return the cached result
if (memo[i][j] != null)
return memo[i][j];
int k = i + j;
boolean result = false;
// Take the current character from s1
if (i < s1.length() && s1.charAt(i) == s3.charAt(k))
result = isInterleaveHelper(s1, s2, s3, i + 1, j, memo);
// Take the current character from s2
if (!result && j < s2.length() && s2.charAt(j) == s3.charAt(k))
result = isInterleaveHelper(s1, s2, s3, i, j + 1, memo);
return memo[i][j] = result;
}
}
Complexity
There are at mostm × n unique states, where m and n are the lengths of s1 and s2. Each state is processed once, resulting in O(m × n) time complexity. The memoization table and recursion stack require
O(m × n) space.