string_segmentation.rb

require 'set'

def segment_string(s, dictionary, solved)
  for i in 1..s.length
    first = s[0, i]
    if dictionary.include?(first)
      second = s[i .. -1]
      if (second.length == 0)
        return true
      end
      if dictionary.include?(second)
        return true
      end
      unless solved.include?(second)
        if segment_string(second, dictionary, solved)
          return true
        end
        solved.add(second)
      end
    end
  end
  false
end

def can_segment_string?(s, dictionary)
  solved = Set.new
  segment_string(s, dictionary, solved)
end

dictionary = Set['hello', 'hell', 'on', 'now']

p can_segment_string?('wellonow', dictionary)