139. 单词拆分 dp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        set<string> st(wordDict.begin(), wordDict.end());
        int len = s.length();
        vector<bool>dp(len+1,false);
        dp[0]=true;
        for(int i=1;i<=len;++i){
            for(int j=i-1;j>=0;--j){
                string latter = s.substr(j,i-j);
                if(st.find(latter)!=st.end() && dp[j]){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[len];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19