Accepted Python DP Solution w/ Explanation


  • 0
    Z

    The question might be simple for many, however it took me quite some time to find a clean and easy way to understand and implement the solution. Thought to share with those that are new like me.

    It's a typical DP question, with additional checks to consider:

    1. dp[i]: The number of ways to decode a substring in S between index 0..(i-1)
    2. dp[i] is the sum of dp[i-1] if
      S[i] is a valid decode, i.e. '1' <= S[i] <= '9', and dp[i-2] if substring S[i-1]S[i] is a valid decode, i.e. '10' <= S[i-1]S[i] <= '26'

    After handling special case, dp[1] = 1 as it contains ways to decode for S[0]. dp[0] is initialized to 1 as well to be used by dp[2] iteration and makes it easier. The code is as below:

    def numDecodings(self, s):
            
            if not s or s[0] == "0": return 0
            
            dp = [0] * (len(s) + 1)
            dp[0] = dp[1] = 1
            for i, c in enumerate(s[1:], 1):
                if c >= "1" and c <= "9": 
                    dp[i+1] = dp[i] 
                if s[i-1:i+1] and s[i-1:i+1] <= "26" and s[i-1:i+1] >= "10" : 
                    dp[i+1] += dp[i-1]
                
            return dp[-1]
                
    

Log in to reply
 

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