2
$\begingroup$

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?

$\endgroup$
3

1 Answer 1

2
$\begingroup$

You can simply maintain a (hash)table, just like in the recursive case. Basically, you need to treat items on the stack like function arguments in recursion. Every time you pop items off the stack for processing, you check whether the particular entry in the table had been filled first. This gives you an equivalent memoized algorithm.

Additionally, you also need to check whether the table already contains the entry when you add an item to the stack; this avoids blowing up the stack with already memoized entries.

maintain a hashtable T of strings.

def num_ways_stack(s: str) -> int:
    stack = deque()
    stack.append(s)
    
    ways = 0
    while stack:
        cur_s = stack.pop()
        if cur_s is in T, then discard cur_s and continue

        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

        if cur_s[1:] is not in T:
            stack.append(cur_s[1:])
        if cur_s[2:] is not in T:
        stack.append(cur_s[2:])
        
    return ways

To answer your second question, which is if there are other methods of converting recursion to iteration, there certainly is. For certain functions that are tail-recursive (and if not, you can try rewriting them into tail-recursive ones using continuous-passing style) you can convert them to equivalent iterative algorithms without keeping a stack but a bunch of variables.

For dynamic programming recurrences, the conventional practice for iterative computation is you identify an order which can be used to correctly fill up the memoization table (e.g. row-major, column-major, or diagonal) and use nested loops to iteratively compute the values in the memoization table. This potentially saves space, as it avoids the need to maintain a stack during the recursion.

$\endgroup$
5
  • 1
    $\begingroup$ thanks for your answer! However, using a hash table to memoize an already computed string requires to keep track of the number of ways that particular string has. How would you do it? I didn't get how you'd fill the hash table. $\endgroup$
    – Yago Tomé
    Aug 30, 2020 at 13:28
  • $\begingroup$ @YagoTomé Not sure I understand you r question. You initialize a hash table, and then gradually fill it out using the procedure described above. This allows you to avoid repeated computation. $\endgroup$ Aug 30, 2020 at 15:19
  • $\begingroup$ The tables don't have to be of fixed size, or you can use something like a trie to store the string arguments. $\endgroup$ Aug 30, 2020 at 15:31
  • $\begingroup$ I mean for example if cur_s is '111', I'd need to have an entry like '111' => 3 since there're 3 ways of decoding 111 (aaa, ak, ka). However, in this stack-based code I only have the solution for strings whose length is 1 (or those which start with 27+). So how can I keep track of the relation num_ways(s) = num_ways(s[1:]) + num_ways(s[2:]) using that hash table? $\endgroup$
    – Yago Tomé
    Aug 30, 2020 at 18:59
  • 1
    $\begingroup$ I agree with OP, this pseudocode never shows anything being added to the hash table and feels incomplete. The point of memoization is that as the call stack unwinds, the memoization table is populated which enables the avoidance of future repeated computations. $\endgroup$
    – ggorlen
    Sep 4, 2020 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.