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.
1class Solution:
2 def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
3 n, m, l = len(s1), len(s2), len(s3)
4 if n + m != l:
5 return False
6 dp = [[False] * (m + 1) for _ in range(n + 1)]
7 dp[0][0] = True
8 for i in range(n + 1):
9 for j in range(m + 1):
10 if i > 0:
11 dp[i][j] = dp[i][j] or (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1])
12 if j > 0:
13 dp[i][j] = dp[i][j] or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
14 return dp[n][m]In the Python implementation, the dynamic programming table dp is filled similarly. The table tracks whether s3[0:i+j] can be formed by s1[0:i] and s2[0:j]. We check each character's addition from either string matches s3.
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#include <string>
#include <unordered_map>
class Solution {
public:
bool isInterleave(std::string s1, std::string s2, std::string s3) {
if (s1.length() + s2.length() != s3.length()) return false;
std::unordered_map<int, bool> memo;
return checkInterleave(s1, 0, s2, 0, s3, 0, memo);
}
private:
bool checkInterleave(const std::string &s1, int i, const std::string &s2, int j, const std::string &s3, int k, std::unordered_map<int, bool> &memo) {
if (k == s3.size()) return true;
int key = i * s3.size() + j;
if (memo.find(key) != memo.end()) return memo[key];
bool ans = false;
if (i < s1.size() && s1[i] == s3[k]) ans = ans || checkInterleave(s1, i + 1, s2, j, s3, k + 1, memo);
if (j < s2.size() && s2[j] == s3[k]) ans = ans || checkInterleave(s1, i, s2, j + 1, s3, k + 1, memo);
return memo[key] = ans;
}
};This C++ solution uses a recursive helper function with memoization. The state of the function is represented by (i, j), and memoization prevents redundant state evaluations.