Leetcode 139 Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

数组dp用来表示到该下标处之前的所有字符是否能被字典中的字符串分解。

dp[j] = dp[i] && s[i+1..j] belongs to dictionary

dp的首个值设0以适合一般情况故指针a,b应用到字符串下标都需要－1

def word_break(s, word_dict)
    dp = Array.new(s.length+1,false) 
    dp[0]= true
    1.upto(s.length) {|b| b.times {|a| dp[b] = true if dp[a] and word_dict.include?s[a..b-1]}}
    dp[-1]
end

Leetcode 139 Word Break

原文：http://www.cnblogs.com/lilixu/p/4571903.html