用于构建Trie数据结构的Ruby代码的说明

所以我有从维基百科中抓取的这个ruby代码，我修改了一下：

@trie = Hash.new() def build(str) node = @trie str.each_char { |ch| cur = ch prev_node = node node = node[cur] if node == nil prev_node[cur] = Hash.new() node = prev_node[cur] end } end build('dogs') puts @trie.inspect 

我首先在控制台irb上运行它，并且每次输出node ，它每次都会给我一个空哈希{} ，但是当我实际调用带有参数'dogs'字符串的函数构建时，它实际上可以工作，并输出{"d"=>{"o"=>{"g"=>{"s"=>{}}}}} ，这是完全正确的。

这可能是一个Ruby问题，而不是关于算法如何工作的实际问题。 我真的没有足够的Ruby知识来破译那里发生的事情。

Answer 1

你可能会迷失在那些混乱的代码中，这种代码采用的方法似乎更适合C ++而不是Ruby。 这是一个更简洁的格式，使用特殊情况Hash进行存储：

 class Trie < Hash def initialize # Ensure that this is not a special Hash by disallowing # initialization options. super end def build(string) string.chars.inject(self) do |h, char| h[char] ||= { } end end end 

它的工作方式完全相同，但指针几乎没有相同的混乱，例如：

 trie = Trie.new trie.build('dogs') puts trie.inspect 

Ruby的Enumerable模块充满了令人惊讶的有用方法，例如inject ，这正是你想要的情况。

Answer 2

我认为你只是错误地使用irb。 您应该输入整个函数，然后运行它，看看是否得到了正确的结果。 如果它不起作用，那么你在这里发布整个IRB会话怎么样。

这里还有一个简化版的代码：

 def build(str) node = @trie str.each_char do |ch| node = (node[ch] ||= {}) end # not sure what the return value should be end