Decode Ways -- LeetCode

 
這道題要求解一個數字串按照字符串編碼方式可解析方式的數量。看到這種求數量的，我們很容易想到動態規劃來存儲前面信息，然後迭代得到最後結果。
我們維護的量res[i]是表示前i個數字有多少種解析的方式，接下來來想想遞歸式，有兩種方式：第一種新加進來的數字不然就是自己比較表示一個字符，那麼解析的方式有res[i-1]種，第二種就是新加進來的數字和前一個數字湊成一個字符，解析的方式有res[i-2]種（因為上一個字符和自己湊成了一個）。當然這裡要判斷前面說的兩種情況能否湊成一個字符，也就是范圍的判斷，如果可以才有對應的解析方式，如果不行，那麼就是0。最終結果就是把這兩種情況對應的解析方式相加。這裡可以把范圍分成幾個區間：
（1）00：res[i]=0（無法解析，沒有可行解析方式）；
（2）10, 20：res[i]=res[i-2]（只有第二種情況成立）；
（3）11-19, 21-26：res[i]=res[i-1]+res[i-2]（兩種情況都可行）；
（4）01-09, 27-99：res[i]=res[i-1]（只有第一種情況可行）；
遞推式就是按照上面的規則來得到，接下來我們只要進行一遍掃描，然後依次得到維護量就可以了，算法的時間復雜度是O(n)。空間上可以看出我們每次只需要前兩位的歷史信息，所以只需要維護三個變量然後迭代賦值就可以了，所以空間復雜度是O(1)。代碼如下：

public int numDecodings(String s) {
    if(s==null || s.length()==0 || s.charAt(0)=='0')
    {
        return 0;
    }
    int num1=1;
    int num2=1;
    int num3=1;
    for(int i=1;i='3')
                num3 = num2;
            else
            {
                if(s.charAt(i-1)=='2' && s.charAt(i)>='7' && s.charAt(i)<='9')
                    num3 = num2;
                else
                    num3 = num1+num2;
            }
        }
        num1 = num2;
        num2 = num3;
    }
    return num2;
}