[LeetCode]题解（python）：091 Decode Ways

题目来源

https://leetcode.com/problems/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.

题意分析

Input: 一个字符串

Output:可以编码的方式数目

Conditions:a到z分别对应1到26

题目思路

采用动态规划的思想，dp初始化为[1,1]，以两个字符来考虑

1）如果10 <= int(s[i-2:i]) <= 26 and s[i - 1] != "0"，说明有两种选择方式，dp[i] = dp[i-1] + dp[i-2]

2）如果刚好等于10或者20，那么dp[i] = dp[i-2]

3）如果s[i-1]不为0，说明不是30，40等数字，dp[i] = dp[i-1]

4）如果不满足以上条件，那么不可能编码成功，返回0

AC代码（Python）

 1 class Solution(object):
 2     def numDecodings(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         if s == "" or s[0] == "0":
 8             return 0
 9         dp = [1,1]
10         for i in range(2, len(s) + 1):
11             if 10 <= int(s[i-2:i]) <= 26 and s[i - 1] != "0":
12                 dp.append(dp[i-1] + dp[i-2])
13             elif int(s[i-2:i]) == 10 or int(s[i-2:i]) == 20:
14                 dp.append(dp[i-2])
15             elif s[i-1] != "0":
16                 dp.append(dp[i-1])
17             else:
18                 return 0
19         return dp[len(s)]
20