class GADDAG
Implementation of the GADDAG
data structure
Attributes
root[R]
The root node
Public Class Methods
new()
click to toggle source
Initializes a GADDAG
@return [GADDAG]
# File lib/gaddag.rb, line 17 def initialize @root = Node.new end
Public Instance Methods
add(word)
click to toggle source
Adds a word to the GADDAG
@param word [String] the word to be added @return [GADDAG] the GADDAG
instance
# File lib/gaddag.rb, line 24 def add(word) @root.create_final_path(word.chars.reverse + [Path::DELIMITER]) Word.new(word.chars).to_delimited_paths.each do |path| @root.create_final_path(path.letters) end self end
find(substring)
click to toggle source
Finds all words that contain the given substring @param substring [String] the substring to search for @return [Array<String>] all matching words
# File lib/gaddag.rb, line 37 def find(substring) first_letter, second_letter, *last_letters = *substring.chars return [] unless @root.path?(last_letters.reverse) @root.follow_path(last_letters.reverse).final_paths.select do |path| path.start_with?([second_letter, first_letter]) end.map do |path| Path.new(last_letters.reverse + path).to_word.to_s end.uniq end