首页 > 代码库 > 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.
- Naive Solution
直接递归实现。
1 bool isInterleave(string s1, string s2, string s3) { 2 int n1 = (int)s1.length(); 3 int n2 = (int)s2.length(); 4 int n3 = (int)s3.length(); 5 6 if (n1 + n2 != n3) { 7 return false; 8 } 9 if (n1 != 0 || n1 != 0) {10 if (n1 && n2) {11 if (s1[0] == s2[0] && s1[0] == s3[0]) {12 return isInterleave(s1.substr(1), s2, s3.substr(1)) || isInterleave(s1, s2.substr(1), s3.substr(1));13 }14 else if (s1[0] == s3[0])15 return isInterleave(s1.substr(1), s2, s3.substr(1));16 else17 return isInterleave(s1, s2.substr(1), s3.substr(1));18 }19 else if (n1) {20 return s1 == s3;21 }22 else {23 return s2 == s3;24 }25 }26 27 return false;28 }
结果可想而知TLE，无法AC。考虑采用迭代重写
1 bool isInterleave(string s1, string s2, string s3) { 2 int n1 = (int)s1.length(); 3 int n2 = (int)s2.length(); 4 int n3 = (int)s3.length(); 5 if (n1 + n2 != n3) return false; 6 int i = 0; 7 int j = 0; 8 9 bool flag = false;10 stack<int> __S1;11 stack<int> __S2;12 stack<int> __S3;13 14 for (int k = 0; k < n3; ++k) {15 if ((i < n1 && s3[k] == s1[i]) && (j < n2 && s3[k] == s2[j])) {16 if (!flag) {17 __S1.push(i);18 __S2.push(j);19 __S3.push(k);20 21 ++i;22 }23 else {24 flag = false;25 ++j;26 }27 }28 else if (i < n1 && s3[k] == s1[i]) {29 ++i;30 }31 else if (j < n2 && s3[k] == s2[j]){32 ++j;33 }34 else {35 if (!__S3.empty()) {36 k = __S3.top();37 --k;38 i = __S1.top();39 j = __S2.top();40 __S3.pop();41 __S2.pop();42 __S1.pop();43 flag = true;44 }45 else return false;46 47 }48 }49 50 return i == n1 && j == n2;51 }
结果对于大集合时间缩短明显，但算法复杂度太高O(2^(N+M)), N为s1的长度，M为s2的长度。考虑Dynamic Programming以减少冗余的计算。
2. Advanced Solution
1 bool isInterleave(string s1, string s2, string s3) { 2 int n1 = (int)s1.length(); 3 int n2 = (int)s2.length(); 4 int n3 = (int)s3.length(); 5 if (n1 + n2 != n3) return false; 6 7 if (n1 == 0 || n2 == 0) { 8 if (n1 == 0) { 9 return s2 == s3;10 }11 else return s1 == s3;12 }13 14 vector<vector<int> > M(n1 + 1, vector<int>(n2 + 1, 0));15 M[0][0] = 1;16 17 for (int i = 1; i <= n1; ++i) {18 if (s1[i-1] == s3[i-1]) {19 M[i][0] = 1;20 }21 else break;22 }23 24 for (int j = 1; j <= n2; ++j) {25 if (s2[j-1] == s3[j-1]) {26 M[0][j] = 1;27 }28 else break;29 }30 31 for (int i = 1; i <= n1; ++i) {32 for (int j = 1; j <= n2; ++j) {33 if (M[i-1][j] && s1[i-1] == s3[i+j-1]) {34 M[i][j] = 1;35 }36 else if (M[i][j-1] && s2[j-1] == s3[i+j-1]) {37 M[i][j] = 1;38 }39 else M[i][j] = 0;40 }41 42 }43 44 return M[n1][n2];45 }
该算法基于以下考虑，若s3.substr(0, i+j)是s1.substr(0, i) 与s2.substr(0, j)的 interleaving string 那么只有两种可能
- s1[i] == s3[i+j-1] 并且 s3.substr(0, i+j-1)是s1.substr(0, i-1) 与 s2.substr(0, j)的 interleaving string
- s2[j] == s3[i+j-1] 并且 s3.substr(0, i+j-1)是s1.substr(0, i)与s2.substr(0, j-1)的 interleaving string
LeetCode Interleaving String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。