# 139. Word Break

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, determine ifscan be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

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

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

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Thoughts:

1. f[i]: weather a there is a valid sequence ends at i.
2. f[i] is true only when there is a j from 0 to i -1 such that f[j] and dictionary contains (s.substr (j, i - j))

Code: Time: O(n^2) (or O(n^3) depending on "contains" implementation) Space: O(n)

``````class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
bool f [n + 1]; fill_n(f, n + 1, false);
// initialize a vector: vector<bool> f (n + 1, false);
f[0] = true;
for(int i = 1; i <= n ; i++){
for(int j = 0 ; j < i; j++){
string pre_word = s.substr(j, i - j);
if(f[j] && find(wordDict.begin(), wordDict.end(),pre_word)!= wordDict.end()){
f[i] = true;
break; // speed up
}
}
}

return f[n];
}
};
``````