首页 > 代码库 > 40. Interleaving String
40. Interleaving String
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.
思想： 动态规划。
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]); 其中，i, j 分别为字符串 s1, s2 的当前长度。
方法一：
class Solution {public: bool isInterleave(string s1, string s2, string s3) { if(s1.size() + s2.size() != s3.size()) return false; if(s1 == "") return s2 == s3; if(s2 == "") return s1 == s3; vector<vector<bool> > DP(s1.size()+1, vector<bool>(s2.size()+1, false)); DP[0][0] = true; for(size_t i = 1; i <= s1.size(); ++i) { DP[i][0] = (DP[i-1][0] && s1[i-1] == s3[i-1]); for(size_t j = 1; j <= s2.size(); ++j) { DP[0][j] = (DP[0][j-1] && s2[j-1] == s3[j-1]); 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[s1.size()][s2.size()]; }};方法二： 进一步优化，空间复杂度， O(min(s1.size(), s2.size()));
class Solution {public: bool isInterleave(string s1, string s2, string s3) { if(s1.length() + s2.length() != s3.length()) return false; if(s1 == "") return s2 == s3; if(s2 == "") return s1 == s3; if(s2.size() > s1.size()) s1.swap(s2); // make the sapce O(min(s1.size(), s2.size())); vector<bool> DP(s2.size()+1); for(size_t i = 0; i <= s1.size(); ++i) { DP[0] = (!i || (DP[0] && s1[i-1] == s3[i-1])); for(size_t j = 1; j <= s2.size(); ++j) { DP[j] = (DP[j] && s1[i-1] == s3[i+j-1]) || (DP[j-1] && s2[j-1] == s3[i+j-1]); } } return DP[s2.size()]; }};
40. Interleaving String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。