139_word_break.rb

# Leetcode Problem: https://leetcode.com/problems/word-break/
# Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
#
#     Note:
#
#     The same word in the dictionary may be reused multiple times in the segmentation.
#     You may assume the dictionary does not contain duplicate words.
#
#         Example 1:
#
#     Input: s = "leetcode", wordDict = ["leet", "code"]
# Output: true
# Explanation: Return true because "leetcode" can be segmented as "leet code".
#
#     Example 2:
#
#     Input: s = "applepenapple", wordDict = ["apple", "pen"]
# Output: true
# Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
#     Note that you are allowed to reuse a dictionary word.
#
#         Example 3:
#
#     Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
# Output: false
# ----------------------------------------------------------------------------------------------------------------------
require 'pry'
# @param {String} string
# @param {String[]} word_dict
# @return {Boolean}
def word_break(string, word_dict)
  data = {}
  word_dict.each do |word|
    data[word] = true
  end
  result = Array.new(string.size + 1, false)
  result[0] = true
  for i in 1..string.size
    for j in 0..i-1
      if result[j] && data[string[j..i-1]]
        result[i] = true
        break
      end
    end
  end
  result[string.size]
end


p word_break("leetcode",  ["leet", "code"])
p word_break("catsandog",  ["cats", "dog", "sand", "and", "cat"])