我有一个散列的散列。这个散列有一个字典。我需要在其中找到具有相同根的所有匹配项。例如,我有:
#<Trie:0x00000001bf9a40 @root={
"m"=>{"a"=>{"x"=>{
:end=>true,
"i"=>{"m"=>{
:end=>true,
"i"=>{"m"=>{"l"=>{"i"=>{"a"=>{"n"=>{:end=>true}}}}}}
}},
"w"=>{"e"=>{"l"=>{"l"=>{:end=>true}}}}
}}}
}>
和单词“max”
、“maxim”
、“maximilian”
、“maxwell”
。我如何通过根获取此哈希中的所有单词?例如
t = Trie.new
t.add( .....# now we added words
t.find('max')
#result all words which begins from 'max'
t.find('maxim')
#result all words which begins from 'maxim' => maxim, maximilian
最佳答案
看起来我的find
方法与@sawa 的非常相似。 (我相信 @sawa 是第一个教我在这种情况下使用 inject
和 &:[]
的人,所以这很合适。)
给定:
class Trie
def initialize(root)
@root = root # Just a shortcut to use your data and focus on your question
end
# Recurses through Hash `h` to find all words starting with `s`
def words(h, s, a=[])
h.each do |k, v|
if k == :end
a << s
else
words(v, s+k, a)
end
end
a
end
private :words
def find(start)
words(start.chars.inject(@root, &:[]), start) rescue []
end
end
t = Trie.new({"m"=>{"a"=>{"x"=>{:end=>true,
"i"=>{"m"=>{:end=>true,
"i"=>{"m"=>{"l"=>{"i"=>{"a"=>{"n"=>{:end=>true}}}}}}}},
"w"=>{"e"=>{"l"=>{"l"=>{:end=>true}}}}}}}})
你可以这样做:
t.find('max')
# => ["max", "maxim", "maximimlian", "maxwell"]
t.find('maxi')
# => ["maxim", "maximimlian"]
t.find('maximi')
# => ["maximimlian"]
t.find('maxw')
# => ["maxwell"]
t.find('x')
# => []
关于ruby 遍历哈希,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17637587/