#include<iostream>
#include<unordered_set>
#include<string>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int len=s.length();
        if(len==0)
            return true;
        int i;
        for(i=1;i<=len;i++)
        {
            if(dict.count(s.substr(0,i))>0&&wordBreak(s.substr(i,len-i),dict))
                return true;
        }
        return false;
    }
};

int main()
{
    unordered_set<string> dict={"aaaa","aaa"};
    Solution s;
    string ss="aaaaaa";
    cout<<s.wordBreak(ss,dict)<<endl;
}

#include<iostream>
#include<unordered_set>
#include<string>
#include<cstring>
using namespace std;

class Solution
{
public:
    bool wordBreak(string s, unordered_set<string> &dict)
    {
        int len=s.length();
        if(len==0)
            return true;
        bool dp[len+1];
        memset(dp,0,sizeof(dp));
        int i,j;
        for(i=1; i<=len; i++)
        {
            if(dp[i]==false&&dict.count(s.substr(0,i))>0)
                dp[i]=true;
            if(i==len&&dp[i]==true)
                return true;
            if(dp[i]==true)
            {
                for(j=i+1; j<=len; j++)
                {
                    if(dp[j]==false&&dict.count(s.substr(i,j-i))>0)
                        dp[j]=true;
                    if(j==len&&dp[j]==true)
                        return true;
                }
            }
        }
        return false;
    }
};

int main()
{
    unordered_set<string> dict= {"leet","code"};
    Solution s;
    string ss = "leetcode";
    cout<<s.wordBreak(ss,dict)<<endl;
}

// 第二版 参考leetcode官网上的答案
class Solution { 
public:
bool wordBreak(string s, unordered_set<string> &dict) {
    vector<bool> wordB(s.length() + 1, false);
    wordB[0] = true;
    for (int i = 1; i < s.length() + 1; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                wordB[i] = true;
                break; //只要找到一种切分方式就说明长度为i的单词可以成功切分，因此可以跳出内层循环。
            }
        }
    }
    return wordB[s.length()];
    }
};