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.

dp就行了。如果要用到前面算到的两个字符的数据，从后往前扫会方便一些。

dp[i]就表示s[i...n-1]的decoding方式的个数。

1. 如果s[i] == '0'的话，那么dp[i]应该为0，也就是初始值；因为以0开始的数字是不能decode的；比如"011"；

2. 如果s[i] != '0'，那么可以将s[i]decode为一个字母，那么dp[i] = dp[i+1];

3. 如果s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')，也就是说s[i...i+1]可以合并起来decode为一个字母，那么dp[i]还要加上dp[i+2]；

4. 初始值。i=n-1时，只要它不等于'0'，那么它可以decode为一个字母，所以dp[i=n-1]=dp[i+1=n]=1; dp[n]=1; 这里为了访问s[i+1]不越界，在一开始还在s后面加上了一个'0'。

 1 class Solution {
 2 public:
 3     int numDecodings(string s) {
 4         int n = s.length(); 
 5         if (n == 0) return 0;
 6         s += '0';
 7         vector<int> dp(n + 2, 0);
 8         dp[n] = 1;
 9         for (int i = n - 1; i >= 0; --i) {
10             if (s[i] != '0') dp[i] = dp[i + 1];
11             if (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')) dp[i] += dp[i + 2];
12         }
13         return dp[0];
14     }
15 };

因为每次只会用到dp[i+1]和dp[i+2]，所以完全可以将这部分空间再优化。

 1 class Solution {
 2 public:
 3     int numDecodings(string s) {
 4         int n = s.length(); 
 5         if (n == 0) return 0;
 6         s += '0';
 7         int ret, n1 = 1, n2 = 0;
 8         for (int i = n - 1; i >= 0; --i) {
 9             ret = 0;
10             if (s[i] != '0') ret = n1;
11             if (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')) ret += n2;
12             n2 = n1;
13             n1 = ret;
14         }
15         return ret;
16     }
17 };

优质内容筛选与推荐>>
1、python——week2语法学习
2、回调函数
3、软件测试术语中英对照- Part O
4、mysql update 语气常用手册
5、图片上传

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

好看

已推荐到看一看

你的朋友可以在“发现”-“看一看”看到你认为好看的文章。

取消 推荐

我知道了

已取消，“好看”想法已同步删除

知道了