# Leetcode 139. Word Break
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/word-break/ 。

想法 :

陣列代表的狀態是這一格能不能成功有字串走過來 : 也就是這個字典裡有沒有這個子字串。
接著枚舉所有字串並更新陣列的狀態。

時間複雜度 : O(s.len * wordDict.size() * wordDict[i].len)

程式碼 :

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int l=wordDict.size(), len_s=s.size(), dp[310]={0}, now=0;
        
        dp[0]=1;
        while(dp[now] == 1 && now < len_s){
            for(int i=0 ; i<l ; i++){
                if(wordDict[i].size() <= len_s-now){
                    string str=s.substr(now,wordDict[i].size());
                    //cout << str << " " << wordDict[i] << endl;
                    
                    if(str == wordDict[i]){
                        dp[now+wordDict[i].size()]=1;
                    }
                }
            }
            
            now++;
            while(dp[now] != 1 && now < len_s){
                now++;
            }
        }
        
        /*for(int i=0 ; i<=len_s ; i++){
            cout << dp[i];
        }*/
        
        return dp[len_s];
    }
};