Why is one approach for backtracking faster than the other?

Question

So I was working on Leetcode on Word Breaking II, and came up with two backtracking implementations that are similar but differ in memoization. However, one will pass the specs while the other would not due to time limit exceeded. Can someone please explain why approach 1 is faster than approach 2?

For context, basically the problem gives me a string and a dictionary. If there are words in the string that are also in the dictionary, separate out the words with a space and place the resulting string (of words) into a resulting array. Dictionary words can be used more than once!

So for example:

s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Approach 1 (works!):

require 'set'

def word_break(s, word_dict)
    word_dict = Set.new(word_dict)

    bt(s, word_dict, 0, {})
end

def bt(s, word_dict, i, mem)
    return mem[i] if mem[i]
    return [''] if i == s.length

    res = []

    j = i

    while j < s.length
        word = s[i..j]

        if word_dict.include?(word)
            word_breaks = bt(s, word_dict, j + 1, mem)
 
            word_breaks.each do |words|
                new_combined_words = word
                new_combined_words += ' ' + words if words.length > 0

                res << new_combined_words
            end
        end

        j += 1
    end

    # Memoizing here makes it fast!
    mem[i] = res
end

Approach 2 (Not fast enough):

require 'set'

def word_break(s, word_dict)
    word_dict = Set.new(word_dict)

    bt(s, word_dict, 0, {})
end

def bt(s, word_dict, i, mem)
    return mem[i] if mem[i]
    return [''] if i== s.length

    res = []

    j = i

    while j < s.length
        word = s[i..j]

        if word_dict.include?(word)
            word_breaks = bt(s, word_dict, j + 1, mem)
 
            word_breaks.each do |words|
                new_combined_words = word
                new_combined_words += ' ' + words if words.length > 0
                
                # Memoizing here but it's too slow
                (mem[i] ||= []) << new_combined_words
                
                res << new_combined_words
            end
        end

        j += 1
    end
    
    res
end

In approach 1, I memoize in the end with mem[i] = res while in approach 2, I memoize on the fly as I am generating new combination of words.

Any assistance would be greatly appreciated, thank you!

Answer 1

When mem[i] happen to be empty array, you would never set it in approach 2. Empty values are not memoized.

What Cary suggested in his comment should fix this. The code is still going to be a bit slower than approach 1, but it will probably pass the tests on leetcode.

UPD: even with that suggested edit, when bt(s, word_dict, j + 1, mem) returns an empty array, we would never memoize mem[i], which is makes the code asymptotically exponential. To fix this, try the following.

         mem[i] ||= []
        
         if word_dict.include?(word)
            word_breaks = bt(s, word_dict, j + 1, mem)
 

            word_breaks.each do |words|
                new_combined_words = word
                new_combined_words += ' ' + words if words.length > 0

                mem[i] << new_combined_words
                
                res << new_combined_words
            end
        end