Word Break -- leetcode

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[i]，表示第i個字元以前是否可以分隔成單詞。 i 從0開始。

已知dp[0..i]時，求dp[i+1]，則需要償試，s[k..i],  0<=k <=i, 進行償試。

在leetcode上實際執行時間為12ms。

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        vector<bool> dp(s.size()+1);
        dp[0] = true;
        for (int i=1; i<=s.size(); i++) {
            for (int j=0; j<i; j++) {
                if (dp[j] && wordDict.find(s.substr(j, i-j)) != wordDict.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};