首页 > 代码库 > 【leetcode】 Interleaving String (hard)
【leetcode】 Interleaving String (hard)
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.
思路：做过几道动态规划了，终于也有了点感觉。一次就AC了，好开心啊~
用dp[m][n]来存储s3[0 ~ m+n-1]是否是s1[0~m-1]与s2[0~n-1]交替组成的。注意，没有必要存s3的维度，因为s1[0~m-1]与s2[0~n-1]只能匹配s3的m+n个字符，即第三个维度是确定的。
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.length(); int len2 = s2.length(); int len3 = s3.length(); if(len3 != len1 + len2) return false; vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false)); dp[0][0] = true; for(int i = 1; i < len1 + 1; i++) { dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1]); } for(int j = 1; j < len2 + 1; j++) { dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1]); } for(int i = 1; i < len1 + 1; i++) { for(int j = 1; j < len2 + 1; j++) { 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]; }};
【leetcode】 Interleaving String (hard)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。