Skip to content

Instantly share code, notes, and snippets.

@arnab arnab/output.txt
Created Feb 16, 2014

Embed
What would you like to do?
$ ruby titleizer.rb
Using iterative approach: ["alexander", "the", "great"]
Using recursive approach: ["alexander", "the", "great"]
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.