pydata

Keep Looking, Don't Settle

leetcode 91. Decode Ways

91. Decode Ways

题目大意：1到26对应A到Z。现在给一个数字，问有多少中解码方式

解题思路：数字1到26只有一位或者两位，所以把数字去掉开始的第一位和第二位，那么原来数字的解码方式就等于去掉一位的解码方式加上去掉两位的解码方式之和。

两个condition：

  1. 空字符串解码方式为0，长度为1的字符串解码方式为1

  2. 0开头的数字解码方式为0，因为数字只有1到26

1. 记忆化递归

在记忆体中，空字符串的解码方式为1.

class Solution(object):
    def numDecodings(self, s):
        if len(s) == 0:
            return 0
        self.m_ways = {}
        self.m_ways[""] = 1

        def ways(s):
            if s in self.m_ways:
                return self.m_ways[s]
            if s[0] == "0":
                return 0
            if len(s) == 1:
                return 1
            w = ways(s[1:])
            prefix = int(s[:2])
            if prefix <= 26:
                w += ways(s[2:])
            self.m_ways[s] = w
            return w
        return ways(s)

2. 记忆化递归, 使用index来考虑子问题

def numDecodings(self, s):
    if len(s) == 0:
        return 0
    self.m_ways = {}
    def ways(s, l, r):
        if l in self.m_ways:
            return self.m_ways[l]
        if s[l] == "0":
            return 0
        if l >= r:
            return 1
        w = ways(s, l + 1, r)
        prefix = int(s[l]) * 10 + int(s[l + 1])
        if prefix <= 26:
            w += ways(s, l + 2, r)
        self.m_ways[l] = w
        return w
    return ways(s, 0, len(s) - 1)