首页 > 代码库 > 97. Interleaving String
97. 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.
public bool IsInterleave(string s1, string s2, string s3) { if(s1 == "") return s2 == s3; if(s2 == "") return s1 == s3; if(s1.Length + s2.Length != s3.Length) return false; return Dp(s1,s2,s3,0,0,0); } private bool Dp(string s1, string s2, string s3, int i1,int i2, int i3) { if(i3 == s3.Length) return true; else if(i1 >= s1.Length && i2 >= s2.Length) return false; else { bool judgeS1 = false; bool judgeS2 = false; if(i1 <s1.Length && s1[i1] == s3[i3]) { judgeS1 = Dp(s1,s2,s3,i1+1,i2,i3+1); } if(judgeS1) return true; if(i2 < s2.Length && s2[i2] == s3[i3]) { judgeS2 = Dp(s1,s2,s3,i1,i2+1,i3+1); } return judgeS2; } }
public bool IsInterleave(string s1, string s2, string s3) { if(s1 == "") return s2 == s3; if(s2 == "") return s1 == s3; if(s1.Length + s2.Length != s3.Length) return false; var dp = new bool[s1.Length+1,s2.Length+1]; dp[0,0] = true; for(int i = 1;i<= s2.Length;i++) { dp[0,i] = dp[0,i-1] && (s2[i-1] == s3[i-1]); } for(int i = 1;i<= s1.Length;i++) { for(int j = 0;j<= s2.Length;j++) { if(j ==0) dp[i,j] = dp[i-1,j] && (s1[i-1] == s3[i-1]); else { dp[i,j] = (dp[i-1,j]&&(s1[i-1] == s3[j+i-1]))|| (dp[i,j-1]&&(s2[j-1] == s3[j+i-1])); } } } return dp[s1.Length,s2.Length]; }
97. Interleaving String
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。