首页 > 代码库 > 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.
算法:使用动态规划,f[i][j]表示s1的前i个字符和s2的前j个字符是否能组成s3的前i+j个字符,f[i][i]=true,条件:f[i-1][j]=true&&s1[i-1]==s3[i+j-1]或者f[i][j-1]=true&&s2[j-1]=s3[i+j-1] 不满足条件则:f[i][j]=false;最后f[s1.size()][s2.size()]即为所求,代码如下:(一开始被各种下标绕晕了,想了半天终于想明白了)
1 class Solution { 2 public: 3 bool isInterleave(string s1, string s2, string s3) { 4 int len1=s1.size(); 5 int len2=s2.size(); 6 int len3=s3.size(); 7 if(len1+len2!=len3) return false; 8 bool f[len1+1][len2+1]; 9 f[0][0]=true;10 for(int i=1;i<=len1;i++)11 {12 if(f[i-1][0]&&s1[i-1]==s3[i-1]) f[i][0]=true;13 else f[i][0]=false;14 }15 for(int i=1;i<len2+1;i++)16 {17 if(f[0][i-1]&&s2[i-1]==s3[i-1]) f[0][i]=true;18 else f[0][i]=false;19 }20 21 for(int i=1;i<=len1;i++)22 {23 for(int j=1;j<=len2;j++)24 {25 if(s1[i-1]==s3[i+j-1]&&f[i-1][j]||s2[j-1]==s3[i+j-1]&&f[i][j-1]) f[i][j]=true;26 else f[i][j]=false;27 }28 }29 return f[len1][len2];30 }31 };
Interleaving String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。