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': 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': 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?