Clean DP python solution using O(1) 46 ms!!!


  • 0
    S

    Please suggest if any one has any better solution.

    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            if(len(s) == 0):
                return 0
            no_of_decodings = 0
            if s[-1] != "0":
                no_of_decodings = 1
            no_of_decodings_prev = -1
            for i in range(len(s)-2,-1,-1):
                if(s[i] == "0"):
                    if no_of_decodings == 0:
                        break
                    no_of_decodings_prev = no_of_decodings
                    no_of_decodings = 0
                    continue
                if int(s[i] + s[i+1]) >= 10 and int(s[i] + s[i+1]) <= 26:
                    if no_of_decodings_prev == -1:
                        no_of_decodings = no_of_decodings + 1
                        no_of_decodings_prev = no_of_decodings - 1
                    else:
                        no_of_decodings = no_of_decodings + no_of_decodings_prev
                        no_of_decodings_prev = no_of_decodings - no_of_decodings_prev
                else:
                    no_of_decodings_prev = no_of_decodings
            return no_of_decodings
    

Log in to reply
 

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