leetcode筆記：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.
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，可使用動態規劃來完成。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    int numDecodings(const string &s) 
    {
        if (s.empty() || s[0] == '0') return 0;
        int prev = 0;
        int cur = 1;
        // 長度為 n 的字符串，有 n+1 個階梯
        for (size_t i = 1; i <= s.size(); ++i) 
        {
            if (s[i-1] == '0') cur = 0;
            if (i < 2 || !(s[i - 2] == '1' ||
               (s[i - 2] == '2' && s[i - 1] <= '6')))
            prev = 0;
            int tmp = cur;
            cur = prev + cur;
            prev = tmp;
        }
    return cur;
    }
};