# 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
=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