Sponsored
Sponsored
This approach uses a dynamic programming table to ascertain whether the third string, s3, is an interleaving of s1 and s2. We use a 2D DP array dp[i][j] which signifies if s3[0:i+j] is an interleaving of s1[0:i] and s2[0:j]. A bottom-up approach is taken to fill this table.
Time Complexity: O(n * m), where n and m are the lengths of s1 and s2, respectively.
Space Complexity: O(n * m), required for the dp array.
1public class Solution {
2 public boolean isInterleave(String s1, String s2, String s3) {
3 int n = s1.length();
4 int m = s2.length();
5 int l = s3.length();
6 if (n + m != l) return false;
7 boolean[][] dp = new boolean[n + 1][m + 1];
8 dp[0][0] = true;
9 for (int i = 0; i <= n; i++) {
10 for (int j = 0; j <= m; j++) {
11 if (i > 0) {
12 dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1));
13 }
14 if (j > 0) {
15 dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
16 }
17 }
18 }
19 return dp[n][m];
20 }
21}This Java solution uses a 2D boolean array dp to keep track of whether it's possible to interleave to form s3. The loop structure is used to check and update cells based on previous valid paths that can form the substring up to i + j.
This recursive approach tries to construct the interleaved string by attempting to use characters from s1 and s2 to match each character of s3. To optimize, memoization is applied to avoid recalculating results for the same subproblems.
Time Complexity: O(n * m), due to memoization allowing only one calculation per subproblem.
Space Complexity: O(n * m) for the memoization table.
1using System.Collections.Generic;
public class Solution {
public bool IsInterleave(string s1, string s2, string s3) {
if (s1.Length + s2.Length != s3.Length)
return false;
return IsInterleave(s1, 0, s2, 0, s3, 0, new Dictionary<string, bool>());
}
private bool IsInterleave(string s1, int i, string s2, int j, string s3, int k, Dictionary<string, bool> memo) {
if (k == s3.Length)
return true;
string key = i + ":" + j;
if (memo.ContainsKey(key))
return memo[key];
bool ans = false;
if (i < s1.Length && s1[i] == s3[k])
ans = IsInterleave(s1, i + 1, s2, j, s3, k + 1, memo);
if (!ans && j < s2.Length && s2[j] == s3[k])
ans = IsInterleave(s1, i, s2, j + 1, s3, k + 1, memo);
memo[key] = ans;
return ans;
}
}The C# solution uses recursion with a dictionary for memoization. It tries to match s3 by incrementally using characters from s1 and s2, storing previous results for quick returns.