Interleaving String -- LeetCode

 
這是一道關於字符串操作的題目，要求是判斷一個字符串能不能由兩個字符串按照他們自己的順序，每次挑取兩個串中的一個字符來構造出來。
像這種判斷能否按照某種規則來完成求是否或者某個量的題目，很容易會想到用動態規劃來實現。
先說說維護量，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]為真，是一個或的關系。所以遞推式可以表示成
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) 時間上因為是一個二維動態規劃，所以復雜度是O(m*n)，m和n分別是s1和s2的長度。最後就是空間花費，可以看出遞推式中只需要用到上一行的信息，所以我們只需要一個一維數組就可以完成歷史信息的維護，為了更加優化，我們把短的字符串放在內層循環，這樣就可以只需要短字符串的長度即可，所以復雜度是O(min(m,n))。代碼如下：

public boolean isInterleave(String s1, String s2, String s3) {
    if(s1.length()+s2.length()!=s3.length())
        return false;
    String minWord = s1.length()>s2.length()?s2:s1;
    String maxWord = s1.length()>s2.length()?s1:s2;
    boolean[] res = new boolean[minWord.length()+1];
    res[0] = true;
    for(int i=0;i動態規劃其實還是有套路的，無非就是找到維護量，然後得到遞推式，接下來看看歷史信息對於空間的需求，盡量優化，會在後面對於動態規劃做一個比較通用的總結哈。