word_break_ii.rb

class Solution
  def initialize
    @known_strings = {}
  end

  def word_break(string, word_dict)
    if @known_strings[string]
      return @known_strings[string]
    end

    result = []

    # dict includes whole string
    if word_dict.include?(string)
      result << string
    end

    (0..string.length - 1).each do |i|
      word = string[0..i]

      if word_dict.include?(word)
        remaining = string[word.length..-1]

        word_break(remaining, word_dict).each do |right_side|
          result << [word, right_side].join(' ')
        end
      end
    end

    unless result.empty?
      @known_strings[string] = result
    end

    result
  end

end

require 'minitest/autorun'

class TestSolution < Minitest::Test
  def setup
    @solution = Solution.new
  end

  def test_one
    s = "abcd"
    dict = ["a","abc","b","cd"]
    assert_equal ["a b cd"], @solution.word_break(s, dict)
  end

  def test_two
    s = "aaaaaaa"
    dict = ["aaaa","aa","a"]
    expected = ["a a a a a a a","aa a a a a a","a aa a a a a","a a aa a a a","aa aa a a a","aaaa a a a","a a a aa a a","aa a aa a a","a aa aa a a","a aaaa a a","a a a a aa a","aa a a aa a","a aa a aa a","a a aa aa a","aa aa aa a","aaaa aa a","a a aaaa a","aa aaaa a","a a a a a aa","aa a a a aa","a aa a a aa","a a aa a aa","aa aa a aa","aaaa a aa","a a a aa aa","aa a aa aa","a aa aa aa","a aaaa aa","a a a aaaa","aa a aaaa","a aa aaaa"]
    assert_equal expected.length, @solution.word_break(s, dict).length
    assert_equal expected.sort, @solution.word_break(s, dict).sort
  end

  def test_three
    s = "a"
    dict = ["a"]
    assert_equal ["a"], @solution.word_break(s, dict)
  end

  def test_four
    s = "bb"
    dict = ["a","b","bbb","bbbb"]
    assert_equal ["b b"], @solution.word_break(s, dict)
  end

  def test_five
    s = "catsanddog"
    dict = ["cat", "cats", "and", "sand", "dog"]
    assert_equal ["cats and dog", "cat sand dog"].sort, @solution.word_break(s, dict)
  end
end