首页 > 代码库 > 【LeetCode】Interleaving String
【LeetCode】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.
可以用递归做，每匹配s1或者s2中任意一个就递归下去。但是会超时。
因此考虑用动态规划做。
s1, s2只有两个字符串，因此可以展平为一个二维地图，判断是否能从左上角走到右下角。
当s1到达第i个元素，s2到达第j个元素:
地图上往右一步就是s2[j-1]匹配s3[i+j-1]。
地图上往下一步就是s1[i-1]匹配s3[i+j-1]。
示例：s1="aa",s2="ab",s3="aaba"。标1的为可行。最终返回右下角。
0 a b
0 1 1 0
a 1 1 1
a 1 0 1
class Solution {public: bool isInterleave(string s1, string s2, string s3) { if(s1.size()+s2.size() != s3.size()) return false; //s1.size()+1 by s2.size()+1 matrix representing path vector<vector<bool> > path(s1.size()+1, vector<bool>(s2.size()+1, false)); path[0][0] = true; for(int i = 0; i < s1.size()+1; i ++) {//row for(int j = 0; j < s2.size()+1; j ++) {//col if(i == 0 && j == 0) //start ; else if(i == 0) //go by s2 path[i][j] = path[i][j-1] && (s2[j-1] == s3[j-1]); else if(j == 0) //go by s1 path[i][j] = path[i-1][j] && (s1[i-1] == s3[i-1]); else path[i][j] = (path[i][j-1] && (s2[j-1] == s3[i+j-1])) || (path[i-1][j] && (s1[i-1] == s3[i+j-1])); } } return path[s1.size()][s2.size()]; }};
【LeetCode】Interleaving String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。