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.
思路
回溯法
- 最简单，也是最容易想到的思路。s1, s2, s3对应的下标分别是i, j, k。初始都指向对应的最后一个字符，
然后判断相等的方式分别进行(i--,k--)或者(j--,k--) - 缺点在于：时间复杂度太大。
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if(len1 + len2 != len3)
return false;
return judge(s1, len1 - 1, s2, len2 - 1, s3, len3 - 1);
}
private:
bool judge(string &s1, int i, string& s2, int j, string &s3, int k)
{
if(i < 0 && j < 0 && k < 0) return true;
if(k < 0) return false;
if(i >= 0 && j >= 0 && s1[i] == s2[j])
{
if(s3[k] != s1[i]) return false;
if(judge(s1, i - 1, s2, j, s3, k - 1) || judge(s1, i, s2, j - 1, s3, k - 1))
return true;
}
else if(i >= 0 && s1[i] == s3[k])
return judge(s1, i - 1, s2, j, s3, k - 1);
else if(j >= 0 && s2[j] == s3[k])
return judge(s1, i, s2, j - 1, s3, k - 1);
return false;
}
};动态规划
- 这其实也是一个很典型的动态规划问题。
- dp[i][j] 表示s3中长度为(i+j)的字符串是否由s1(0-i), s2(0-j)重构而成。若可以，取ture，
否则为false - dp[i][j] 中 i = 0 || j = 0, 表示有一个空串
- dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) ||
(dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]));
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if(len1 + len2 != len3)
return false;
vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false));
for(int i = 0; i <= len1; ++i)
{
for(int j = 0; j <= len2; ++j)
{
if(i == 0 && j == 0)
dp[i][j] = true;
else if(i == 0)
{
dp[i][j] = dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]);
}
else if(j == 0)
{
dp[i][j] = dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1]);
}
else
{
dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) || (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]));
}
}
}
return dp[len1][len2];
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
