首页 > 代码库 > 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.
地址：https://oj.leetcode.com/problems/interleaving-string/
算法：比较复杂的动态规划。dp[i][j][k]表示S3[0~i]是否可以由字符串S1[0~j-1]以及字符串S2[0~k-1]相交得到，并且i,j,k必须满足i+1=j+k。所以对于dp[0]，我们只需要初始化dp[0][1][0]以及dp[0][0][1]这两种，然后从dp[1]开始，从j可以取得的最大值开始，由于知道了i，j我们就可以求出k，这样我们就可以通过以下两种情况来求dp[i][j][k]的值，第一种状况，S3[i] 是否等于 S1[j-1]；第二种，S3[i]是否等于S2[k-1]。代码：
1 class Solution { 2 public: 3 bool isInterleave(string s1, string s2, string s3) { 4 if(s1.size() + s2.size() != s3.size()) 5 return false; 6 if(s3.empty()) 7 return true; 8 int len_s3 = s3.size(); 9 int len_s1 = s1.size();10 int len_s2 = s2.size();11 vector<vector<vector<bool> > > dp(len_s3,vector<vector<bool> >(len_s1+1,vector<bool>(len_s2+1)));12 if(len_s1 > 0 && s3[0] == s1[0])13 dp[0][1][0] = 1;14 else if(len_s1 > 0)15 dp[0][1][0] = 0;16 if(len_s2 > 0 && s3[0] == s2[0])17 dp[0][0][1] = 1;18 else if(len_s2 > 0)19 dp[0][0][1] = 0;20 for(int i = 1; i < len_s3; ++i){21 int most_s1 = min(i+1,len_s1);22 int least_s1 = max(0,i-len_s2+1);23 for(int j = most_s1; j >= least_s1 && i+1-j <= len_s2; --j){24 dp[i][j][i+1-j] = (j > 0 && dp[i-1][j-1][i+1-j] && s3[i] == s1[j-1]) || (i-j+1 > 0 && dp[i-1][j][i-j] && s3[i] == s2[i-j]);25 }26 }27 return dp[len_s3-1][len_s1][len_s2];28 }29 int min(int a, int b){30 return a>b ? b : a;31 }32 int max(int a, int b){33 return a>b? a : b;34 }35 };
LeetCode: Interleaving String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。