1 題目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

在孝南等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都做網(wǎng)站、網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需搭建網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),成都全網(wǎng)營銷,成都外貿(mào)網(wǎng)站建設(shè)公司,孝南網(wǎng)站建設(shè)費(fèi)用合理。

'A' -> 1'B' -> 2...'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

接口:public int numDecodings(String s);

2 思路

一維動態(tài)規(guī)劃,偷懶了，照搬博文。
分析：需要注意的是，如果序列中有不能匹配的0，那么解碼方法是0，比如序列012 、100（第二個0可以和1組成10，第三個0不能匹配）。

• 遞歸的解法很容易，但是大集合會超時。轉(zhuǎn)換成動態(tài)規(guī)劃的方法，假設(shè)dp[i]表示序列s[0...i-1]的解碼數(shù)目

  動態(tài)規(guī)劃方程如下：

• 初始條件：dp[0] = 1, dp[1] = (s[0] == '0') ? 0 : 1

• dp[i] = ( s[i-1] == 0 ? 0 : dp[i-1] ) + ( s[i-2,i-1]可以表示字母 ？ dp[i-2] : 0 )， 其中第一個分量是把s[0...i-1]末尾一個數(shù)字當(dāng)做一個字母來考慮，第二個分量是把s[0...i-1]末尾兩個數(shù)字當(dāng)做一個字母來考慮

復(fù)雜度: Time O(n); Space O(n)

3 代碼

        public int numDecodings(String s) {        // 1.初始化
        final int len = s.length();        if (len == 0)            return 0;        int[] dp = new int[len + 1];
        dp[0] = 1;        if (s.charAt(0) != '0')
            dp[1] = 1;        else
            dp[1] = 0;        // 2.一維DP方程
        for (int i = 2; i <= len; i++) {            if (s.charAt(i - 1) != '0')
                dp[i] = dp[i - 1];            else
                dp[i] = 0;            if (s.charAt(i - 2) == '1'
                    || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))
                dp[i] += dp[i - 2];
        }        return dp[len];
    }

4 總結(jié)

寫遞歸的解法

新航道雅思