Skip to content

Instantly share code, notes, and snippets.

@heath

heath/rubyx01.md Secret

Last active December 22, 2015 15:19
Show Gist options
  • Save heath/89af4da8712288ddc0c3 to your computer and use it in GitHub Desktop.
Save heath/89af4da8712288ddc0c3 to your computer and use it in GitHub Desktop.

I'm looking at https://en.wikipedia.org/wiki/Trie#A_Ruby_version

Line 9 seems useless since line 10 is there. For each character in the string, create a key,value pair where the key is the character and the value is a new hash. If the key has been created, assign it a value of the character instead of an empty hash, but then the very next line the parent hash is set to either an empty hash or a character. It doesn't seem right for some reason, and I was hoping someone here with a little time on their hands would slap some sense into me

class Trie
def initialize
@root = Hash.new
end
def build(str)
node = @root
str.each_char do |ch|
node[ch] ||= Hash.new
node = node[ch]
end
node[:end] = true
end
def find(str)
node = @root
str.each_char do |ch|
return nil unless node = node[ch]
end
node[:end] && true
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment