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.

難度：87.這是一道關于字符串操作的題目，要求是判斷一個字符串能不能由兩個字符串按照他們自己的順序，每次挑取兩個串中的一個字符來構造出來。像這種判斷能否按照某種規則來完成求是否或者某個量的題目，很容易會想到用動態規劃來實現。

動態規劃重點在于找到：維護量，遞推式。維護量通過遞推式遞推，最后往往能得到想要的結果

先說說維護量，res[i][j]表示用s1的前i個字符和s2的前j個字符能不能按照規則表示出s3的前i+j個字符，如此最后結果就是res[s1.length()][s2.length()]，判斷是否為真即可。接下來就是遞推式了，假設知道res[i][j]之前的所有歷史信息，我們怎么得到res[i][j]。可以看出，其實只有兩種方式來遞推，一種是選取s1的字符作為s3新加進來的字符，另一種是選s2的字符作為新進字符。而要看看能不能選取，就是判斷s1(s2)的第i(j)個字符是否與s3的i+j個字符相等。如果可以選取并且對應的res[i-1][j](res[i][j-1])也為真，就說明s3的i+j個字符可以被表示。這兩種情況只要有一種成立，就說明res[i][j]為真，是一個或的關系。所以遞推式可以表示成

 1 public class Solution { 2     public boolean isInterleave(String s1, String s2, String s3) { 3         if (s3.length() != s1.length() + s2.length()) return false; 4         if (s1=="" && s2=="" && s3=="") return true; 5         boolean[][] res = new boolean[s1.length()+1][s2.length()+1]; 6         for (int i=0; i<=s1.length(); i++) { 7             for (int j=0; j<=s2.length(); j++) { 8                 if (i==0 && j==0) res[i][j] = true; 9                 else if (i>0 && j==0) res[i][j] = res[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1);10                 else if (i==0 && j>0) res[i][j] = res[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1);11                 else {12                     res[i][j] = res[i-1][j] && s1.charAt(i-1)==s3.charAt(i+j-1) || res[i][j-1] && s2.charAt(j-1)==s3.charAt(i+j-1);13                 }14             }15         }16         return res[s1.length()][s2.length()];17     }18 }

時間上因為是一個二維動態規劃，所以復雜度是O(m*n)，m和n分別是s1和s2的長度。最后就是空間花費，可以看出遞推式中只需要用到上一行的信息，所以我們只需要一個一維數組就可以完成歷史信息的維護，為了更加優化，我們把短的字符串放在內層循環，這樣就可以只需要短字符串的長度即可，所以復雜度是O(min(m,n))。

別人的一維數組做法：(沒懂)

 1 public boolean isInterleave(String s1, String s2, String s3) { 2     if(s1.length()+s2.length()!=s3.length()) 3         return false; 4     String minWord = s1.length()>s2.length()?s2:s1; 5     String maxWord = s1.length()>s2.length()?s1:s2; 6     boolean[] res = new boolean[minWord.length()+1]; 7     res[0] = true; 8     for(int i=0;i<minWord.length();i++) 9     {10         res[i+1] = res[i] && minWord.charAt(i)==s3.charAt(i);11     }12     for(int i=0;i<maxWord.length();i++)13     {14         res[0] = res[0] && maxWord.charAt(i)==s3.charAt(i);15         for(int j=0;j<minWord.length();j++)16         {17             res[j+1] = res[j+1]&&maxWord.charAt(i)==s3.charAt(i+j+1) || res[j]&&minWord.charAt(j)==s3.charAt(i+j+1);18         }19     }20     return res[minWord.length()];21 }

在用這種方法之前我也嘗試過用Recursion，結果TLE了，Recursion代價果然比Iteration大

 1 public class Solution { 2     public boolean isInterleave(String s1, String s2, String s3) { 3         if (s3.length() != s1.length() + s2.length()) return false; 4         boolean[][] res = new boolean[s1.length()+1][s2.length()+1]; 5         res[0][0] = true; 6         return helper(s1.length(), s2.length(), res, s1, s2, s3); 7     } 8      9     public boolean helper(int n1, int n2, boolean[][] res, String s1, String s2, String s3) {10         if (res[n1][n2]) return true;11         if (n1 > 0) {12             res[n1-1][n2] = helper(n1-1, n2, res, s1, s2, s3);13         }14         if (n2 > 0) {15             res[n1][n2-1] = helper(n1, n2-1, res, s1, s2, s3);16         }17         if (n1>0 && res[n1-1][n2] && s1.charAt(n1-1)==s3.charAt(n1+n2-1) || n2>0 && res[n1][n2-1] && s2.charAt(n2-1)==s3.charAt(n1+n2-1)) {18             return true;19         }20         else return false;21     }22 }