Decode Ways

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def numDecodings(self, string):
        self.prefixes = [str(num) for num in range(1, 27)]
        return self.dfs(string, 0, {})

    def dfs(self, string, startIdx, memo):
        if startIdx in memo:
            return memo[startIdx]

        isDecoded = startIdx == len(string)

        if isDecoded:
            return 1

        numDecodings = 0
        undecodedPartOfString = string[startIdx:]

        for prefix in self.prefixes:
            if undecodedPartOfString.startswith(prefix):
                nextStartIdx = startIdx + len(prefix)
                numDecodings += self.dfs(string, nextStartIdx, memo)

        memo[startIdx] = numDecodings

        return numDecodings

Learn

#Memoization

#Dynamic Programming

Videos