Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'
.
I could simply count it using a recursive function as follows:
def num_ways(s: str) -> int:
if len(s) > 0 and s[0] == '0':
return 0
if len(s) <= 1:
return 1
if len(s) >= 2 and int(s[:2]) > 26:
return num_ways(s[1:])
return num_ways(s[1:]) + num_ways(s[2:])
However, this function can be easily optimized by using memoization technique. (I'll avoid showing off memoization into that code to keep it tidy, but you can assume I could use such a decorator that would be responsible for this job)
Alright! But what if I want to use a stack to replace that recursion? (I don't want to use a bottom-up dynamic programming approach in this case)
So I could have something like this:
def num_ways_stack(s: str) -> int:
stack = deque()
stack.append(s)
ways = 0
while stack:
cur_s = stack.pop()
if len(cur_s) > 0 and cur_s[0] == '0':
continue
if len(cur_s) <= 1:
ways += 1
continue
if len(cur_s) >= 2 and int(cur_s[:2]) > 26:
stack.append(cur_s[1:])
continue
stack.append(cur_s[1:])
stack.append(cur_s[2:])
return ways
It works! But how can I optimize it by memoizing duplicate work as well as I'm able to do in the recursive method? Moreover, is there a better way to convert from a recursive function to a stack-based non-recursive one?