Given strings s1, s2, s3, determine whether s3 is formed by an interleaving of s1 and s2.
Input: s1="aabcc", s2="dbbca", s3="aadbbcbcac" → Output: trueInput: s1="aabcc", s2="dbbca", s3="aadbbbaccc" → Output: false
dp[i][j] = true if s3[0..i+j-1] can be formed by interleaving s1[0..i-1] and s2[0..j-1]. Transition: dp[i][j] = (dp[i-1][j] && s1[i-1]==s3[i+j-1]) || (dp[i][j-1] && s2[j-1]==s3[i+j-1]).
- If len(s1)+len(s2) != len(s3) return false.
- dp[0][0] = true. Initialize first row and column.
- Fill dp table using the recurrence.
- Return dp[m][n].
class Solution {
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];
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)