Very very very simple Python solution using Top-down DP


  • 1
    class Solution(object):
        def numDecodings(self, s):
    
            def search(s, memo):
                if s in memo:
                    return memo[s]
                if len(s) <= 1:
                    return 1 if s != "0" else 0
                res, n, i = 0, len(s), 1
                while i <= n and 1 <= int(s[:i]) <= 26:
                    res += search(s[i:], memo)
                    i += 1
                memo[s] = res
                return res
    
            if s == "":
                return 0
            return search(s, {})

  • 0

    Alternative solution using bottom-up DP:

    def search_dp(s):
        n = len(s)
        DP = [0] * n + [1]
        for i in range(n - 1, -1, -1):
            if s[i] != "0":
                DP[i] += DP[i + 1]
            if i < n - 1 and 10 <= int(s[i:i+ 2]) <= 26:
                DP[i] += DP[i + 2]
        return DP[0]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.