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 };

?

轉載于:https://www.cnblogs.com/sqxw/p/4007977.html

總結

以上是生活随笔為你收集整理的Interleaving String的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。