ruby​​ trie执行参考问题

Question

我想在Ruby中实现一个trie，但无法弄清楚我的print + collect方法存在什么问题。

我刚刚在JS中实现了相同的功能，并且工作正常，我的工作状态为。我想这个问题可能是Ruby通过引用传递（与JS不同）以及Ruby中变量赋值的工作方式。

所以，如果我有string.clone作为参数运行的代码时，我递归调用collect函数然后我得到：

["peter", "peter", "petera", "pdanny", "pdjane", "pdjanck"] 

，如果我通过string则：

["peterradannyjaneck", "peterradannyjaneck", "peterradannyjaneck", "peterradannyjaneck", "peterradannyjaneck", "peterradannyjaneck"] 

任何要想法如何解决这个问题？

代码：

class Node 
    attr_accessor :hash, :end_node, :data 

    def initialize 
    @hash = {} 
    @end_node = false 
    @data = data 
    end 

    def end_node? 
    end_node 
    end 
end 

class Trie 
    def initialize 
    @root = Node.new 
    @words = [] 
    end 

    def add(input, data, node = @root) 
    if input.empty? 
     node.data = data 
     node.end_node = true 
    elsif node.hash.keys.include?(input[0]) 
     add(input[1..-1], data, node.hash[input[0]]) 
    else 
     node.hash[input[0]] = Node.new 
     add(input[1..-1], data, node.hash[input[0]]) 
    end 
    end 

    def print(node = @root) 
    collect(node, '') 
    @words 
    end 

    private 

    def collect(node, string) 
    if node.hash.size > 0 
     for letter in node.hash.keys 
     string = string.concat(letter) 
     collect(node.hash[letter], string.clone) 
     end 

     @words << string if node.end_node? 
    else 
     string.length > 0 ? @words << string : nil 
    end 
    end 
end 

trie = Trie.new 
trie.add('peter', date: '1988-02-26') 
trie.add('petra', date: '1977-02-12') 
trie.add('danny', date: '1998-04-21') 
trie.add('jane', date: '1985-05-08') 
trie.add('jack', date: '1994-11-04') 
trie.add('pete', date: '1977-12-18') 
print trie.print 

Answer 1

Ruby的string concat变异字符串并不会返回一个新的字符串。您可能需要改为+ operator。所以基本上改变2线内敛的for循环按如下：

stringn = string + letter 
collect(node.hash[letter], stringn) 

此外，你可能想要么总是初始化@words在print空调用collect之前，或使它成为一个局部变量print和通它到collect。