微軟面試題: LeetCode 91. 解碼方法 出現次數:3

題目描述:

一條包含字母 A-Z 的消息通過以下方式進行了編碼:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
給定一個只包含數字的非空字元串,請計算解碼方法的總數。

 

示例 1:

輸入:s = “226”
輸出:3
解釋:它可以解碼為 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 2:

輸入:s = “0”
輸出:0

 

分析:

  因為 s[0:i] 的解碼方案 可以由 s[0:i-1] 的解碼方案 和 s[i] 的值推導得到

所以 可以使用動態規劃演算法解決。下面具體分析:

  給定 數字字元串 “1226” ,去掉最後一位得到子串 “122”  ,”122″ 可解碼

為 1,2,2   12,2   1,22   三種,”1226″的解碼方案 是將字元 ‘6’ 加到 “122”的所有解碼方案中

對1,2,2 生成”1226″的解碼序列 有兩種選擇,’6′ 單獨作一位加在後面  1,2,2,6 

或 ‘6’ 和 最後一位2拼接成  1,2,26 。由 “122”的解碼方案 生成 “1226”的解碼方案有

1,2,2,6   1,2,26  12,2,6  12,26   1,22,6

即可以根據 s[0:i-1] 的解碼方案 和 s[i] 的值推出 s[0:i] 的解碼方案。需要特別考慮 s[i-1] 和 s[i] 為 ‘0’ 的情況。

1. 定義狀態   dp[i] :s[0 : i]  的所有解碼, np[i] s[0 : i]  的所有解碼中,最後一個編碼是1位的解碼,如 對 “122” 

的解碼  1,2,2   12,2   1,22     dp[2] =  3 ,np[2] = 2 。

狀態轉移和 狀態空間壓縮 見下面程式碼和注釋:

 1 class Solution {
 2 public:
 3     int numDecodings(string s) 
 4     {
 5         int dp ;
 6         int np ;
 7         //base case 
 8         if(s[0] == '0'){
 9              dp = 0;
10              np = 0;
11         }
12         else
13         {
14             dp = 1;
15             np = 1;
16         }
17         //state move
18         for(int i = 1;i < s.size();++i)
19         {
20             if(s[i-1] == '0')//s[0:i-1] 有效的結尾只可能是 10,20,
21             {
22                 if(s[i] == '0') //『0』 既不能拼接在 10,20 後面,也 單獨作一位
23                 {
24                     dp = 0;
25                     np = 0;
26                 }
27                 //非『0』 可以單獨作一位
28                 else
29                 {
30                    if(dp > 0)//單獨作一位跟在 『10』 『20』 後面
31                    {
32                        // dp = dp;
33                         np = dp;
34                    }
35                    else//s[0:i-1] 沒有合法的解碼方法
36                    {
37                        dp = 0;
38                        np = 0;
39                    }  
40                 }
41             }
42             else if(s[i] == '0') // s[i-1] != '0' ,s[i] == '0'
43          // s[i] == '0' 只能在 s[i-1]是 1或2 的時候與之拼接成『10』或』20『,不能在其他情況下拼接,也不能單獨作一位  
44             {
45                 if(s[i-1] == '1' || s[i-1] == '2') //s[i-1]是 1或2 的時候與之拼接成『10』或』20『
46                 {
47                     dp = np;
48                     np = 0;
49                 }
50                 else
51                 {
52                     dp = 0;
53                     np = 0;
54                 }
55             } 
56             //s[i]和s[0:i-1]的所有解碼序列 即可拼接又可單獨作一位 
57             else if(s[i-1] == '1' || (s[i-1] == '2' && s[i] >= '1' && s[i] <= '6'))
58             {
59                int temp = dp;
60                 dp = dp + np;
61                 np = np + (temp - np);
62             }
63             // s[i-1] 不是 0,1,2  s[i] 不是0,s[i]只能單獨作一位
64             else
65             {//dp 不變 所有的s[0:i-1]的 2位結尾的解碼,全部都變成 1位結尾的解碼,1位結尾的解碼依然是一位結尾的解碼
66               //  dp = dp;
67                 np = dp;
68             }
69         }
70         return dp;
71     }
72 };