-1

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"}}}}>
4

1 回答 1

0

在我看来,问题出在这一行:

node[:end] = "#{word}"

这里你node[:end]只能是一个单词,如果两个单词有相同的 t9 键序列,它会被覆盖。试试这个:

(node[:end] ||= []) << word

这样,您将在分支的末尾有一个单词数组。不要忘记检查单词是否已经在 trie 中。

于 2013-09-04T22:42:13.923 回答