Short and fast backtracking + caching solution


  • 1
    A
    def word_break(s, word_dict, hash = nil)
        return [""] if s.to_s.empty?
        hash ||= {}
        return hash[s] if !hash[s].nil?
        hash[s] = word_dict
                  .select { |x| s.start_with?(x) }
                  .map { |x| 
                         word_break(s[x.size..-1], word_dict, hash)
                         .map { |y| "#{x} #{y}".strip }
                  }
                  .flatten
    end

Log in to reply
 

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