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

Analyse: Difine dp[i] is whether S[0...i] can be segmented, thus dp[i] is true means that s[0,...k], s[k + 1, ....i] can be segmented, where 0 < k < i. 

dp[i] = dp[k] && wordDict.find(s.substr(k + 1, i - k)) != wordDict.end(). 

Runtime: 16ms.

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        string newstr = "#" + s;
        int len = newstr.size();
        vector<bool> dp(len, false);
        
        dp[0] = true;
        for(int i = 1; i < len; i++){
            for(int k = 0; k < i; k++){
                dp[i] = dp[k] && wordDict.find(newstr.substr(k + 1, i - k)) != wordDict.end();
                if(dp[i]) break; //s[0...i] can be segmented
            }
        }
        return dp[len - 1];
    }
};