#include <iostream>

#include <string>

#include <vector>

#include <unordered_set>

using namespace std;

/*

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".

*/

class Solution {

public:

    bool wordBreak(string s, unordered_set<string> &dict) {

        if(s.size() ==  || dict.size() == )

            return false;

        int len = s.size();

        vector<bool> dp(len+, false);//保存状态，dp[i]表示前i个字符是否可以进行wordBread

        dp[] = true;

        for(int i = ; i <= len; i++)

            for(int j = ; j < i; j++)

            {

                if(dp[j] && dict.count(s.substr(j, i-j)) == )//对前i个字符进行切分时，只要有一种情况为true，则dp[i]=true

                {

                    dp[i] = true;

                    break;

                }

            }

        return dp[len];

    }

    bool wordBreak2(string s, unordered_set<string> &dict) {

        if(s.size() ==  || dict.size() == )

            return false;

        int len = s.size();

        vector<bool> dp(len+, false);//保存状态，dp[i]表示前i个字符是否可以进行wordBread

        dp[] = true;

        for(int i = ; i < len; i++)

            if(dp[i])

            {

                for(int j = ; j <= len-i; j++)

                    if(dict.count(s.substr(i, j)) == )

                        dp[i+j] = true;

            }

        return dp[len];

    }

    //DP：自顶向下，

    int wordBreak3_core(string s, unordered_set<string> &dict, int *dp)

    {

        int len = s.size();

        if(dp[len] >= )

            return dp[len];//如果值已经改变即不再是初始值，说明dp[len]已经求得，直接返回即可，不必再求

        int isBreak;

        if(len == )

            isBreak = ;

        else

        {

            int ret = ;

            for(int i = ; i < len; i++)

            {

                if(wordBreak3_core(s.substr(, i), dict, dp) ==  && dict.count(s.substr(i, len-i)) == )

                {

                    ret = ;

                    break;

                }

            }

            isBreak = ret;

        }

        dp[len] = isBreak;

        return isBreak;

    }

    //DP：自顶向下，

    bool wordBreak3(string s, unordered_set<string> &dict)

    {

        if(s.size() ==  || dict.size() == )

            return false;

        int len = s.size();

        int *dp = new int[len+];//保存状态，dp[i]表示前i个字符是否可以进行wordBread

        for(int i = ; i <= len; i++)

            dp[i] = -;//每个状态进行初始化

        int ret = wordBreak3_core(s, dict, dp);

        delete [] dp;

        return ret;

    }

};

int main(void)

{

    string s("leetcode");

    unordered_set<string> dict;

    dict.insert("leet");

    dict.insert("code");

    Solution solution;

    bool ret = solution.wordBreak3(s, dict);

    cout<<ret<<endl;

    return ;

}

class Solution {

public:

    class Node {

    public:

        Node* next[];

        bool end;

        Node(): end(false) { for (int i = ; i < ; i++) next[i] = NULL;}

        void insert(string a) {

            Node * cur = this;

            for (int i = ; i < a.size(); i++) {

                if (cur->next[a[i]-'a'] == NULL) {

                    cur->next[a[i]-'a'] = new Node();

                }

                cur = cur->next[a[i]-'a'];

            }

            cur->end = true;

        }

        ~Node () {

            for (int i = ;i < ; i++) delete next[i];

        }

    };

    bool wordBreak(string s, unordered_set<string> &dict) {

        Node root;

        for (auto it = dict.begin(); it != dict.end(); ++it) {

            root.insert(*it);

        }

        vector<bool> v(s.size(), false);

        findMatch(s, &root, , v);

        for (int i = ; i < s.size(); i++)

            if (v[i]) findMatch(s, &root, i+, v);

        return v[s.size() - ];

    }

    void findMatch(const string& s, Node* cur, int start, vector<bool> &v) {

        int i = start, n = s.size();

        while (i < n) {

            if (cur->next[s[i] - 'a'] != NULL) {

                if (cur->next[s[i] - 'a']->end) v[i] = true;

                cur = cur->next[s[i] - 'a'];

            }

            else break;

            i++;

        }

    }

};