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];
    }
};