Ruby Trie Implementierung Referenz Ausgabe

Question

Ich versuche, einen Trie in Ruby zu implementieren, aber kann nicht herausfinden, was das Problem mit meinen print + collect Methoden ist.

Ich habe gerade das gleiche in JS implementiert und funktioniert gut. Ich vermute, das Problem könnte sein, dass Ruby als Referenz übergeben wird (anders als JS) und wie die Variablenzuweisung in Ruby funktioniert.

Also, wenn ich den Code mit string.clone als Argument ausgeführt werden, wenn ich die dann collect Funktion rekursiv rufe ich:

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

und wenn ich pass string dann:

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

Irgendwelche Ideen, wie man repariere das?

der Code:

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

Rubys string concat mutiert die Zeichenfolge und gibt keinen neuen String. Vielleicht möchten Sie stattdessen die + operator. Also im Grunde die zwei Linien innerhalb for-Schleife Collect ändern nach unten:

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

Auch möchten Sie wahrscheinlich entweder immer @words initialisieren in print zu leeren, bevor collect Aufruf oder eine lokale Variable machen in print und Pass es zu collect.