forked from netsetos/python_code
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDecode_Ways(Recursion)
More file actions
49 lines (38 loc) · 1.22 KB
/
Decode_Ways(Recursion)
File metadata and controls
49 lines (38 loc) · 1.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
RECURSION
def numDecodings(A,index):
#when character is empty string
if index==len(A):
return 1
#when only character is 0
if A[index] == "0":
return 0
#when single character
if index == len(A)-1:
return 1
way1=numDecodings(A,index+1)
way2=0
if int(A[index:index+2]) <=26:
way2=numDecodings(A,index+2)
return way1+way2
MEMOIZATION
A="1112"
arr= [0 for i in range(len(A)+1)]
def numDecodings_memo(A,index,arr):
#when character is empty string
if index==len(A):
return 1
#when only character is 0
if A[index] == "0":
return 0
#when single character
if index == len(A)-1:
return 1
if arr[index]>0:
return arr[index]
way1=numDecodings_memo(A,index+1,arr)
way2=0
if int(A[index:index+2]) <=26:
way2=numDecodings_memo(A,index+2,arr)
arr[index]= way1+way2
return arr[index]
print(numDecodings_memo(A,0,arr))