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 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分别和1到26的数字一一对应，给定一串用字符表示的数字，将数字串从不同位置拆开，每一个数字都对应一个字符，如此构成了一个字母字符串.
- 从不同的位置拆分数字字符串，可以得到不同的字母字符串，问一共有多少种有效的拆分方式.
思路
- 此题目同70. Climbing Stairs思路非常类似.
- 假设我们已经知道了一个包含两个数字可以有多少种拆分方式，当加入第三个数字时：
- 此数字可以直接添加到原来两个字符的所有拆分方案末尾
- 或者此数字与前一个数字构成一个新的数字，插入到第一个数字构成的所有方案的末尾,即
D(i) = D(i-1) + D(i-2)D(i)=D(i−1)+D(i−2)
- 此数字不能与两个数字构成新的数字，因为这样一定构成了三位数，超出了有效范围.
- 我们还要注意构成的数字的有效性质
1.如果当前数字为0，构成的数字无效.
2.如果与前面一个数字构成的范围不在10到26（包括两端）之间,构成的数字无效.
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2018-12-25 22:56:32 # @Last Modified by: 何睿 # @Last Modified time: 2018-12-26 10:50:02 class Solution: def numDecodings(self, s): """ :type s: str :rtype: int """ length = len(s) # 如果只有一个字符且部位则返回1 if length == 1 and 1 <= int(s) <= 26: return 1 # 如果只有一个字符且该字符为'0',则返回0 elif length == 1: return 0 pretwo = 1 if int(s[0]) else 0 temp = int(s[0:2]) # 如果第二个数是0，则没有可行的解码方案 if temp < 10: preone = 0 # 如果前两个字符构成的数字在11到19之间（包括两端），或在21到26之间（包括两端） # 则有一种解码方案 elif 11 <= temp <= 19 or 21 <= temp <= 26: preone = 2 # 如果前两个数构成的数字是10，20或者大于26的数且不是10的倍数 # 则只有一种解码方案 elif temp == 10 or temp == 20 or (temp > 26 and int(s[1]) != 0): preone = 1 # 其他情况没有一种解码方案 else: preone = 0 res = preone # 当前位置的解码方案=上一个位置的解码方案数+上两个位置的解码方案数 for i in range(2, length): # 如果当前位置是字符0，说明当前位置与(去掉当前字符，前面所有字符构成的字符串)的 # 所有解码方案不能组成新的方案，当前方案数置为0 if s[i] == '0': preone = 0 # 如果当前位置与前一个位置构成的两位数不在10到26之间（包括两端） # 则当前位置不能与(去掉当前字符和前一个字符，前面所有字符构成的字符串)的 # 所有解码方案不能组成新的方案，当前方案数置为0 if not 10 <= int(s[i-1:i+1]) <= 26: pretwo = 0 # 当前位置的解码方案为前两个位置解码方案之和 res = preone+pretwo pretwo = preone preone = res return res if __name__ == "__main__": so = Solution() res = so.numDecodings("12") print(res)
源代码文件在这里.
