1 題目

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

在孝南等地區，都構建了全面的區域性戰略布局，加強發展的系統性、市場前瞻性、產品創新能力，以專注、極致的服務理念，為客戶提供成都做網站、網站建設 網站設計制作按需搭建網站,公司網站建設,企業網站建設,成都品牌網站建設,成都全網營銷,成都外貿網站建設公司,孝南網站建設費用合理。

'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 思路

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

• 遞歸的解法很容易，但是大集合會超時。轉換成動態規劃的方法，假設dp[i]表示序列s[0...i-1]的解碼數目

  動態規劃方程如下：

• 初始條件：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]末尾一個數字當做一個字母來考慮，第二個分量是把s[0...i-1]末尾兩個數字當做一個字母來考慮

復雜度: 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 總結

寫遞歸的解法

新航道雅思

網頁名稱：leetcode面試準備:DecodeWays
瀏覽路徑：http://m.newbst.com/article38/jeejsp.html

成都網站建設公司_創新互聯，為您提供手機網站建設、網站設計公司、商城網站、做網站、網站建設、定制開發

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯