output.txt

$ ruby titleizer.rb
Using iterative approach: ["alexander", "the", "great"]
Using recursive approach: ["alexander", "the", "great"]

titleizer.rb

# d = Dictionary.new
class Dictionary
  def words
    @words ||= %w{alexander the great}
  end

  def exact_word?(str)
    words.include? str
  end

  # d.deadend?("ale") => false
  # d.deadend?("le") => true
  def deadend?(prefix)
    words_starting_with(prefix).empty?
  end

  # d.words_starting_with("ale") => ["alexander"]
  # d.words_starting_with("le") => []
  # d.words_starting_with("th") => ["the"]
  # d.words_starting_with("the") => ["the"]
  def words_starting_with(prefix)
    # "alexander".index(Regexp.new('^' + 'ale')) => 0
    # "alexander".index(Regexp.new('^' + 'le')) => nil
    re = Regexp.new('^' + prefix)
    words.reject {|w| w.index(re).nil?}
  end
end

def dictionary
  @dict ||= Dictionary.new
end

def find_words_iteratively(str)
  combinations = []
  0.upto(str.size - 1) do |i|
    i.upto(str.size - 1) do |j|
      current_prefix = str[i..j]
      next if dictionary.deadend?(current_prefix)
      combinations << current_prefix
    end
  end
  combinations.select {|w| dictionary.exact_word? w}
end
puts "Using iterative approach: " + find_words_iteratively("alexanderthegreat").inspect

def find_words_recursively(full_str, str, acc=[], current_prefix="", pos=0)
  return acc if pos == full_str.size

  fst = str[0]
  rest = str[1..-1]

  if str.empty? || dictionary.deadend?(current_prefix)
    find_words_recursively(full_str, full_str[pos+1..-1], acc, "", pos+1)
  else
    current_prefix = current_prefix + fst
    acc << current_prefix
    find_words_recursively(full_str, rest, acc, current_prefix, pos)
  end
end
str = "alexanderthegreat"
words = find_words_recursively(str, str).select {|w| dictionary.exact_word? w}
puts "Using recursive approach: " + words.inspect