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