DecodeWays-L91

• This approach is a recursive brute force approach which is based on the tree based on the tree based approach.
• For every character it can either behave as single or two digits within some contraints.
• Also this is a recursive approach where each it process the whole of string by taking each char once in combination of one or two digits.
• The two char combination is checked for constraints of :
  • no 0 as its first character .
  • 1 place character should be less than 7 if the 0^th character is 2. ( This is to check characters from 1 to 26)
• If the no of character is only one then it has reached to the end of the string with taking each characters under consideration.
  • So one, 1 is returned for that branch of tree.
  • So for each complete branch only one is added.

class Solution:
    def numDecodings(self, s: str) -> int:
        def dfs(i):
            if i==len(s):
                return 1
            if s[0] =='0':
                return 0
            res = dfs(i+1
            if(i<len(s)-1):
                if(s[i]=='1' or s[i]=='2' and s[i+1]<'7'):
                    res+=dfs(i+2)
            return res
        return dfs(0)

n = "12345"

eval = Solution()
out1 = eval.numDecodings(n)
print(out1)

• This is using the Dynamic Programming Approach
• This creates a memory to save the already calcualted value so that recalculation is avoided .
  • This is done by keeping a dictionalry named dp.
• First the value of dp is initialized by the len(s) value which is not a normal case as len(s) char doesnot exits in the string.
• Then in the tree (dfs) it will look for the value for i in dp, if it is already present then no need to calculate it.
• Then if it is not present then check for if it is 0, as it is the invalid case .
• If both the conditions passes then it will look for case with single digit.
• Also after checking for the double digit and its contraints(no first char to be 0 and no second char to be grater than 6), it calculates for 2 digits too.
• And all the results are accumulated in res variable.
• The program starts from 0^th digit.

class Solution:
    def numDecodings(self, s: str) -> int:
      dp = {len(s):1}
      def dfs(i):
          # print("temp ->",i,":",dp)

          if(i in dp):
              print("dp->",i,"->",dp[i])
              return dp[i]
          if (s[i]=="0"):
              return 0
          print("s[",i,"]->",s[i])
          res = dfs(i+1)
          if(i+1<len(s)) and(s[i]=="1" or (s[i]=="2" and s[i+1] in "0123456")):
              print("Here->",s[i],",",s[i+1])
              res += dfs(i+2)
          dp[i] = res
          print("temp ->",i,":",dp)
          return res

      return dfs(0)
n = "12345234"
eval = Solution();
out1 = eval.numDecodings(n)
print("Result",out1)

s[ 0 ]-> 1
s[ 1 ]-> 2
s[ 2 ]-> 3
s[ 3 ]-> 4
s[ 4 ]-> 5
s[ 5 ]-> 2
s[ 6 ]-> 3
s[ 7 ]-> 4
dp-> 8 -> 1
temp -> 7 : {8: 1, 7: 1}
temp -> 6 : {8: 1, 7: 1, 6: 1}
Here-> 2 , 3
dp-> 7 -> 1
temp -> 5 : {8: 1, 7: 1, 6: 1, 5: 2}
temp -> 4 : {8: 1, 7: 1, 6: 1, 5: 2, 4: 2}
temp -> 3 : {8: 1, 7: 1, 6: 1, 5: 2, 4: 2, 3: 2}
temp -> 2 : {8: 1, 7: 1, 6: 1, 5: 2, 4: 2, 3: 2, 2: 2}
Here-> 2 , 3
dp-> 3 -> 2
temp -> 1 : {8: 1, 7: 1, 6: 1, 5: 2, 4: 2, 3: 2, 2: 2, 1: 4}
Here-> 1 , 2
dp-> 2 -> 2
temp -> 0 : {8: 1, 7: 1, 6: 1, 5: 2, 4: 2, 3: 2, 2: 2, 1: 4, 0: 6}
Result 6

• This is a variant of dynamic programming a bit different from the above implementation from the second approach.
• Here it starts from the last entry and get to the first char.

class Solution:
    def numDecodings(self, s: str) -> int:
        dp = {len(s):1}

        for i in range(len(s)-1, -1, -1):

            if(s[i]=='0'):
                dp[i]= 0
            else:
                dp[i] = dp[i+1]
            if((i+1)<len(s) and (s[i] == '1' or
            (s[i]=='2' and s[i+1] in '0123456'))):
                dp[i] += dp[i+2]
        return dp[0]

n='1222'
eval = Solution()
out1 = eval.numDecodings(n)
print(out1)

5