Ruby Trie 实现参考问题

Question

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

我只是在JS中实现了相同的功能并且工作正常。我想问题可能是 Ruby 是通过引用传递的(与 JS 不同(以及变量赋值在 Ruby 中的工作方式。

因此，如果我在递归调用collect函数时以string.clone作为参数运行代码，那么我会得到：

["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 的字符串 concat 会改变字符串并且不会返回新字符串。您可能需要改用 + 运算符。所以基本上更改集合的 for 循环中的 2 行，如下所示：

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

此外，您可能希望在调用collect之前始终将@words初始化为print中的空，或者使其成为print中的局部变量并将其传递给collect。