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.
1#include <stdbool.h>
2#include <string.h>
3
4bool isInterleave(char * s1, char * s2, char * s3) {
5 int n = strlen(s1);
6 int m = strlen(s2);
7 int l = strlen(s3);
8 if (n + m != l) return false;
9 bool dp[n + 1][m + 1];
10 memset(dp, false, sizeof dp);
11 dp[0][0] = true;
12 for (int i = 0; i <= n; i++) {
13 for (int j = 0; j <= m; j++) {
14 if (i > 0) {
15 dp[i][j] = dp[i][j] || (dp[i - 1][j] && s1[i - 1] == s3[i + j - 1]);
16 }
17 if (j > 0) {
18 dp[i][j] = dp[i][j] || (dp[i][j - 1] && s2[j - 1] == s3[i + j - 1]);
19 }
20 }
21 }
22 return dp[n][m];
23}We initialize a 2D boolean array dp. Each element dp[i][j] is set to true if the substring s3[0:i+j] can be formed by interleaving s1[0:i] and s2[0:j]. We fill this array based on whether we can reach it by taking characters from either s1 or s2.
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.
1
Python's implementation utilizes the @lru_cache decorator to memoize recursive results automatically. It recurses through ranges of characters, checking if continuing would result in an interleave.