[LintCode] Decode Ways 解码方法

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## [LintCode] Decode Ways 解码方法

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.

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

LeetCode上的原题，请参见我之前的博客Decode Ways

```class Solution {
public:
/**
* @param s a string,  encoded message
* @return an integer, the number of ways decoding
*/
int numDecodings(string& s) {
if (s.empty()) return 0;
int n = s.size();
vector<int> dp(n + 2, 1);
for (int i = 2; i < n + 2; ++i) {
if (s[i - 2] == '0') dp[i] = 0;
else dp[i] = dp[i - 1];
if (i >= 3 && (s[i - 3] == '1' || (s[i - 3] == '2' && s[i - 2] <= '6'))) {
dp[i] += dp[i -2];
}
}
return dp.back();
}
};```

```class Solution {
public:
/**
* @param s a string,  encoded message
* @return an integer, the number of ways decoding
*/
int numDecodings(string& s) {
if (s.empty()) return 0;
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int i = 1; i < dp.size(); ++i) {
if (s[i - 1] >= '1' && s[i - 1] <= '9') dp[i] += dp[i - 1];
if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
dp[i] += dp[i - 2];
}
}
return dp.back();
}
};```

```class Solution {
public:
/**
* @param s a string,  encoded message
* @return an integer, the number of ways decoding
*/
int numDecodings(string& s) {
if (s.empty() || s.front() == '0') return 0;
int c1 = 1, c2 = 1;
for (int i = 1; i < s.size(); ++i) {
if (s[i] == '0') c1 = 0;
if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
c1 = c1 + c2;
c2 = c1 - c2;
} else {
c2 = c1;
}
}
return c1;
}
};```

本文转自博客园Grandyang的博客，原文链接：解码方法[LintCode] Decode Ways ，如需转载请自行联系原博主。

+ 关注