Confused about why the recursive version is so much more complicated than the iterative with a memo


  • 0
    T

    The iterative version with a memo:

    def num_decodings(s)
      return 0 if s.length == 0
      n = s.length
      memo = Array.new(n+1,0)
      memo[n] = 1
      memo[n-1] = s[n-1]=="0" ? 0 : 1
      (0...n-1).to_a.reverse.each do |i|
        next if s[i] == "0"
        memo[i] = s[i...(i+2)].to_i <= 26 ? memo[i+1] + memo[i+2] : memo[i+1]
      end
      return memo[0]
    end
    

    The recursive version: As you can see the base case is incredibly complicated.

    def num_decodings(s)
        #puts "s: #{s}"
        return 0 if s.length == 0
        return 0 if s[0] == "0"
        return 1 if s.length == 1
        return 1 if s.length == 2 && s[1] == "0" && s.to_i <= 26
        return 0 if s.length == 2 && s[1] == "0" && s.to_i > 26
        return 2 if s.length == 2 && s.to_i <= 26
        return 1 if s.length == 2
        @ways ||= {}
        return @ways[s] if @ways[s]
        if s[0..1] == "10"
            @ways[s] = num_decodings(s[2..-1])
        elsif s[0..1].to_i <= 26 
            @ways[s] = num_decodings(s[1..-1]) + num_decodings(s[2..-1])
        else
            @ways[s] = num_decodings(s[1..-1])
        end
        #puts @ways
        return @ways[s]
    end
    

    Can someone help me understand why the recursive solution has such a complicated base case when the memoized version is much cleaner?

    I'm assuming it's because my recursive base cases are not simplified enough but maybe there's another reason.


  • 0
    T

    I think you have a little too much logic going on. This could be shortened a bit more I'm sure.

    public int help(String s, int inc) {
        if (s.length() == 0) return inc;
        else if (s.charAt(0) == '0') return 0;
        else if (s.length() >= 2 && (s.charAt(0) == '1' || s.charAt(0) == '2' && s.charAt(1) <= '6')) return help(s.substring(1), 1) + help(s.substring(2), 1);
        return help(s.substring(1), 1);
    }
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.