Description
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
Example
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
Idea
Use dynamic programming, for s1[:i] and s2[:j], we can check if they can be interleaved to s3[:i + j] by asking s1[:i - 1], s2[:j], and s1[:i], s2[:j - 1]. Space can be optimized by storing two rolling rows.
Solution
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int m = s1.size(), n = s2.size();
if (s3.size() != m + n) return false;
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int j = 1; j <= n; ++j) {
dp[j] = dp[j - 1] && s2[j - 1] == s3[j - 1];
}
for (int i = 1; i <= m; ++i) {
vector<bool> dp2(n + 1, false);
for (int j = 0; j <= n; ++j) {
if (i && dp[j] && s1[i - 1] == s3[i + j - 1]) dp2[j] = true;
if (j && dp2[j - 1] && s2[j - 1] == s3[i + j - 1]) dp2[j] = true;
}
dp = dp2;
}
return dp[n];
}
};
101 / 101 test cases passed.
Runtime: 4 ms
