Leetcode: Implement Trie (Prefix Tree)

By | 2018 年 8 月 16 日

Implement a trie with insert, search, and startsWith methods.

Examples:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

Analyze

Check the Trie tree definition: wiki link

  • each node contains a value, records the prefix of the sub tree.
  • each node has a flag to indicate if it’s a target word or not.
  • each node may contain 26 sub nodes, from a-z.

Notes

  • attr_accessor, assign instance attr in class should do with self.var = value or @var = value, var = value won’t work.

Solutions

Ruby

class Node
    attr_accessor :value, :is_target, :sub_nodes

    def initialize(v = '')
        @value = v
        @is_target = false
        @sub_nodes = {}
    end

    def find(key)
        @sub_nodes[key]
    end

    def find_or_create(key, value)
        @sub_nodes[key] ||= Node.new(value)
    end

    def target!
        @is_target = true
    end

    def target?
        @is_target
    end
end

class Trie
    attr_accessor :root

=begin
    Initialize your data structure here.
=end
    def initialize()
        @root = Node.new
    end

    def walk_through(word, create_node = false, &block)
        node = root
        word.each_char do |c|
            node = if create_node
                node.find_or_create(c, node.value + c)
            else
                node.find(c)
            end
            break if node.nil?
        end
        yield node if block_given?
    end

=begin
    Inserts a word into the trie.
    :type word: String
    :rtype: Void
=end
    def insert(word)
        walk_through(word, true) do |node|
            node.target!
        end
    end

=begin
    Returns if the word is in the trie.
    :type word: String
    :rtype: Boolean
=end
    def search(word)
        walk_through(word) do |node|
            return !node.nil? && node.target?
        end
    end


=begin
    Returns if there is any word in the trie that starts with the given prefix.
    :type prefix: String
    :rtype: Boolean
=end
    def starts_with(prefix)
        walk_through(prefix) do |node|
            return !node.nil?
        end
    end
end

发表评论

电子邮件地址不会被公开。 必填项已用*标注