Ruby recursive solution, beats 100%


  • 0
    T
    class WordDictionary
        def initialize
            @root = Node.new
        end
    
        # @param {string} word
        # @return {void}
        # Adds a word into the data structure.
        def add_word(word)
            node = @root
            word.each_char do |c|
                node.children[c] ||= Node.new
                node = node.children[c]
            end
            node.finish = true
        end
    
        # @param {string} word
        # @return {boolean}
        # Returns if the word is in the data structure. A word could
        # contain the dot character '.' to represent any one letter.
        def search(word, node=nil)
            node ||= @root
            return node.finish if word.length == 0
            if word[0] == '.'
                results = node.children.map do |k,v|
                    search(word[1..-1],v)
                end
                return results.any?
            else
                return false if node.children[word[0]].nil?
                return search(word[1..-1],node.children[word[0]])
            end
        end
    end
    
    class Node
        attr_accessor :children, :finish
        def initialize
            @children = {}
            @finish = false
        end
    end
    

Log in to reply
 

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