91 Decode Ways 解碼方法

Description:
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example:

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

題目描述:
一條包含字母 A-Z 的消息通過以下方式進(jìn)行了編碼：

'A' -> 1
'B' -> 2
...
'Z' -> 26
給定一個(gè)只包含數(shù)字的非空字符串，請(qǐng)計(jì)算解碼方法的總數(shù)。

示例 :

示例 1:

輸入: "12"
輸出: 2
解釋: 它可以解碼為 "AB"（1 2）或者 "L"（12）。

示例 2:

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

思路:

動(dòng)態(tài)規(guī)劃
dp[i + 1] = s[i] == '0' ? 0 : dp[i]
如果前一位和該位在 1-26之間:
dp[i + 1] = dp[i] + dp[i - 1]
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)

代碼:
C++:

class Solution 
{
public:
    int numDecodings(string s) 
    {
        int result = s.size() == 0 ? (s[0] == '0' ? 0 : 1) : 1;
        int one = result, two = 0;
        for (int i = 0; i < s.size(); i++)
        {
            result = s[i] == '0' ? 0 : one;
            if (i > 0 and (s[i - 1] == '1' or s[i - 1] == '2' and s[i] < '7')) result += two;
            two = one;
            one = result;
        }
        return result;
    }
};

Java:

class Solution {
    public int numDecodings(String s) {
        int result = s.length() == 0 ? (s.charAt(0) == '0' ? 0 : 1) : 1;
        int one = result, two = 0;
        for (int i = 0; i < s.length(); i++)
        {
            result = s.charAt(i) == '0' ? 0 : one;
            if (i > 0 && (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2' && s.charAt(i) < '7')) result += two;
            two = one;
            one = result;
        }
        return result;
    }
}

Python:

class Solution:
    def numDecodings(self, s: str) -> int:
        last, result = 1, int(s[0] != '0')
        for i in range(1, len(s)):
            last, result = result, last * (9 < int(s[i - 1:i + 1]) < 27) + result * (int(s[i]) > 0)
        return result