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 mutates the string and doesn't return a new string. You may want the + operator 代替。所以基本上改变 collect 的 for 循环内的 2 行如下：

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

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

ruby trie实现参考问题

ruby trie implementation reference issue

ruby

algorithm

tree

trie

data-structures