#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <set>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //将所有单词放入set集合中
        set<string> wordSet;
        for(auto word : wordDict) {
            wordSet.insert(word);
        }

        // 初始化 dp 数组
        bool dp[s.size()+1];
        // 全部初始化为 false
        memset(dp, false, sizeof(dp));
        dp[0] = true;
        for(int i = 1; i <= s.size(); ++i) {
            for(int j = 0; j < i && !dp[i]; ++j) {
                dp[i] = dp[j] && wordSet.find(s.substr(j, i-j)) != wordSet.end();
            }
        }
        return dp[s.size()];
    }
};

int main()
{
    string str = "leetcode";
    vector<string> wordDict;
    wordDict.push_back("leet");
    wordDict.push_back("code");
    Solution obj;
    cout<<obj.wordBreak(str, wordDict)<<endl;
    return 0;
}