Decode Ways -- leetcode

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.

基本思路

和问题 Climbing Stairs 类似

第i位之前，decode共有两种途径：

1. 第i-1位能独立decode

2. 第i-2 和 i-1位，两位一起被当作个整体decode

则deocde方法数，为上面两个途径之和。

此代码在leetcode上，实行执行时间为5ms。

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty()) return 0;
        int w2 = 1;
        int w1 = s[0] != '0' ? 1 : 0;
        int w = w1;
        for (int i=2; i<=s.size(); i++) {
            w = (s[i-1] == '0') ? 0 : w1;
            if (s[i-2] == '1' || s[i-2] == '2' && s[i-1] >= '0' && s[i-1] <= '6')
                w += w2;
            
            w2 = w1;
            w1 = w;
        }
        return w;
    }
};

Decode Ways -- leetcode

原文：http://blog.csdn.net/elton_xiao/article/details/45310013