[Leetcode] Word Break

Problem

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".

Algorithm

Let dp[i] indicates whether s.substring(0,i) can be separated. For the s.substring(0,i), it can be broke at position j, such that s.substring(j,i) is a word in the dictionary, 0 <= j < i. We have the recurrence

                                     dp[i] = OR(dp[j] And s.substring(j,i) is in dict), 0 <= j < i.

Code