LeetCode 91. Decode Ways

简介: 字母A到Z分别和1到26的数字一一对应,给定一串用字符表示的数字,将数字串从不同位置拆开,每一个数字都对应一个字符,如此构成了一个字母字符串.从不同的位置拆分数字字符串,可以得到不同的字母字符串,问一共有多少种有效的拆分方式.

v2-ba76359f3a1b515091aba2c515b269e4_1440w.jpg

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)


源代码文件在这里.


目录
相关文章
|
存储
LeetCode 394. Decode String
给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
96 0
LeetCode 394. Decode String
|
Java Python
LeetCode 394:字符串解码 Decode String
题目: 给定一个经过编码的字符串,返回它解码后的字符串。Given an encoded string, return its decoded string. 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。
1025 0
LeetCode 92 Decode Ways
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51339103 ...
689 0
LeetCode 91 Decode Ways(编码方式)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51340198 ...
971 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
57 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2