首页 > 代码库 > [LeetCode]Interleaving String关于遍历和动态规划
[LeetCode]Interleaving String关于遍历和动态规划
晚上做了一下leetcode的Interleaving String，觉得特别适合比较树的遍历和动态规划的效率比较。
题目如下：
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
第一反应很适合用递归:
bool isInterleave_res(string s1, string s2, string s3) { if ((s1.empty() && s2.empty() && s3.empty()) || (!s1.empty() && !s3.empty() && s3[0] == s1[0] && isInterleave_res(s1.substr(1, s1.length()-1), s2, s3.substr(1, s3.length()-1))) || (!s2.empty() && !s3.empty() && s3[0] == s2[0] && isInterleave_res(s1, s2.substr(1, s2.length()-1), s3.substr(1, s3.length()-1))) ) { return true; } return false; }
这样本质上就是树的深度优先遍历，但是效率就比较低，很多节点会多次计算到，果然TLE，用例是：
s1 = "bbbbbabbbbabaababaaaabbababbaaabbabbaaabaaaaababbbababbbbbabbbbababbabaabababbbaabababababbbaaababaa";
s2 = "babaaaabbababbbabbbbaabaabbaabbbbaabaaabaababaaaabaaabbaaabaaaabaabaabbbbbbbbbbbabaaabbababbabbabaab";
s3 = "babbbabbbaaabbababbbbababaabbabaabaaabbbbabbbaaabbbaaaaabbbbaabbaaabababbaaaaaabababbababaababbababbbababbbbaaaabaabbabbaaaaabbabbaaaabbbaabaaabaababaababbaaabbbbbabbbbaabbabaabbbbabaaabbababbabbabbab";
这题很容易也想到用动态规划，设置表dp，dp[i][j]代表s1的前i个和s2的前j个能和s3的前i+j个匹配上，则根据dp[i][j]就可以推出dp[i+1][j]和dp[i][j+1]。返回dp最右下角的值。
例如题目中的例子1：s3 = "aadbbcbcac"
例子2：s3 = "aadbbcbccc"
class Solution {public: bool isInterleave(string s1, string s2, string s3) { int len1 = s1.length(), len2 = s2.length(), len3=s3.length(); if (len1+len2!=len3) { return false; } vector<vector<bool>> dp(len1+1, vector<bool>(len2+1, false)); dp[0][0] = true; for (int i = -1; i < len1; ++i) { for (int j = -1; j < len2; ++j) { if (dp[i+1][j+1]==true) { if (i+1 < len1 && i+j+2 < len3 && s1[i+1]==s3[i+j+2]) { dp[i+2][j+1] = true; } if (j+1 < len2 && i+j+2 < len3 && s2[j+1]==s3[i+j+2]) { dp[i+1][j+2] = true; } } } } return dp[len1][len2]; }};
这样代码就通过了。
仔细观察，这题用遍历就是一棵二叉树的深度优先遍历，而这棵树对应dp的表格就是(i, j)的左节点就是(i+1, j)右节点是(i, j+1)，所以(i+1, j)的右节点和(i, j+1)的左节点是同样的(i+1, j+1)，进一步加剧了遍历树的重复。
但是观察dp表，其实也浪费了很多，如果s1长度为m而s2长度为n，DP的时间复杂度和空间复杂度都为m*n(空间复杂度可以优化为2×m或者2×n，因为只和上一行相关)，但是其实我们关心的只是其中为T的点，最好情况下其实只需要m+n。
我们可以将树的遍历（只走了为T的点）和DP表结合起来，可以理解为将DP表用稀释矩阵的形式保存，只保存T的点，而走过的T点就不再遍历，这样在m和n很大的情况下应该有较大提升，代码如下：
class Solution {public: bool isInterleave(string s1, string s2, string s3) { int len1 = s1.length(), len2 = s2.length(), len3=s3.length(); if (len1+len2!=len3) { return false; } stack<pair<int, int>> node; set<pair<int, int>> passed; node.push(pair<int, int>(-1, -1)); pair<int, int> last_node; int count = 0; while (!node.empty()) { count++; int i = node.top().first; int j = node.top().second; passed.insert(pair<int, int>(i, j)); if (i == len1-1 && j == len2-1) { return true; } node.pop(); if (i+1 < len1 && i+j+2 < len3 && s1[i+1]==s3[i+j+2] && passed.find(pair<int, int>(i+1, j)) == passed.end()) { node.push(pair<int, int>(i+1, j)); } if (j+1 < len2 && i+j+2 < len3 && s2[j+1]==s3[i+j+2] && passed.find(pair<int, int>(i, j+1)) == passed.end()) { node.push(pair<int, int>(i, j+1)); } } return false; }};
三种方法，第一种，Time Limit Exceeded；第二种16ms通过所有测试用例，第三种8ms
[LeetCode]Interleaving String关于遍历和动态规划