Ruby version Trie method


  • 0
    B
    def replace_words(dict, sentence)
        root = Trie.new
        dict.each do |word|
            root.insert(word)
        end
        res = []
        sentence = sentence.split(' ')
        sentence.each do |word|
            idx = root.shortest_index(word)
            res << word[0..idx]
        end
        return res.join(' ')
    end
    
    class TrieNode
        attr_accessor :is_word, :children
        def initialize
            @is_word = false
            @children = {}
        end
    end
    
    class Trie
        def initialize
            @root = TrieNode.new
        end
        
        def insert(word)
            node = @root
            word.chars.each do |ch|
                node = (node.children[ch] ||= TrieNode.new)
            end
            node.is_word = true
            nil
        end
        
        def shortest_index(word)
            node = @root
            word.chars.each_with_index do |ch, i|
                break if !node.children.key?(ch)
                return i if node.children[ch].is_word
                node = node.children[ch]
            end
            return word.size - 1
        end
    end
    

Log in to reply
 

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