Problem
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example 1:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Solution
/**
* @param {string} s1
* @param {string} s2
* @param {string} s3
* @return {boolean}
*/
var isInterleave = function(s1, s2, s3) {
var dp = {};
if (s3.length !== s1.length + s2.length) return false;
return helper(s1, s2, s3, 0, 0, 0, dp);
};
var helper = function (s1, s2, s3, i, j, k, dp) {
var res = false;
if (k >= s3.length) return true;
if (dp['' + i + j + k] !== undefined) return dp['' + i + j + k];
if (s3[k] === s1[i] && s3[k] === s2[j]) {
res = helper(s1, s2, s3, i + 1, j, k + 1, dp) || helper(s1, s2, s3, i, j + 1, k + 1, dp);
} else if (s3[k] === s1[i]) {
res = helper(s1, s2, s3, i + 1, j, k + 1, dp);
} else if (s3[k] === s2[j]) {
res = helper(s1, s2, s3, i, j + 1, k + 1, dp);
}
dp['' + i + j + k] = res;
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n^2).
n
为s3.length
。 - Space complexity : O(n^2).