T9 trie 生成器的这种实现有一个重大缺陷。它覆盖之前添加到树中的单词,而不是附加它们。我对此并不感到惊讶,只是被难住了......
class Trie
def initialize
@root = Hash.new
end
# do a for loop here
def build(word)
node = @root
t9num = word.tr('a-z', '22233344455566677778889999')
t9num.each_char do |ch|
node[ch] ||= Hash.new
node = node[ch]
end
node[:end] = "#{word}"
end
def find(str)
node = @root
str.each_char do |ch|
return nil unless node = node[ch]
end
node[:end] && true
end
end
这些命令:
t = Trie.new
t.build('buy')
t.build('build')
t.build('builder')
t.build('act')
t.build('acu')
puts t.inspect
输出这个:
#<Trie:0x0000010103ea60 @root={"2"=>{"8"=>{"9"=>{:end=>"buy"}, "4"=>{"5"=>{"3"=>{:end=>"build", "3"=>{"7"=>{:end=>"builder"}}}}}}, "2"=>{"8"=>{:end=>"acu"}}}}>