问答

当前位置

Decode ways的DFS解法

  • by LC
  • 1
  • 6 月,3 周前
  • Ta: 李助教

助教您好,因为我没上过动态规划班,这道题我就用DFS + Memo 的方式去做了。想请问下,这种做法,时间复杂度应该是多少呢?谢谢。

class Solution:
    """
    @param s: a string,  encoded message
    @return: an integer, the number of ways decoding
    """
    def numDecodings(self, s):
        # write your code here
        if s is None or len(s) == 0:
            return 0

        self.memo = {}
        return self.helper(s, 0)

    def helper(self, s, index):
        if index == len(s):
            return 1

        if index in self.memo:
            return self.memo[index]

        if s[index] == '0':
            return 0

        sum = 0

        for i in range(index, index + 2):
            if i < len(s):
                prefix = s[index : i + 1]
                if int(prefix) > 26:
                    continue

                sum += self.helper(s, i + 1)

        self.memo[index] = sum

        return sum

1 个回复

2019-04-20 助教-York

时间和空间复杂度都是O(n)

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1