<p>Given a string <code>s</code> and a dictionary of strings <code>wordDict</code>, return <code>true</code> if <code>s</code> can be segmented into a space-separated sequence of one or more dictionary words.</p>

<p><strong>Note</strong> that the same word in the dictionary may be reused multiple times in the segmentation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;, wordDict = [&quot;leet&quot;,&quot;code&quot;]
<strong>Output:</strong> true
<strong>Explanation:</strong> Return true because &quot;leetcode&quot; can be segmented as &quot;leet code&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;applepenapple&quot;, wordDict = [&quot;apple&quot;,&quot;pen&quot;]
<strong>Output:</strong> true
<strong>Explanation:</strong> Return true because &quot;applepenapple&quot; can be segmented as &quot;apple pen apple&quot;.
Note that you are allowed to reuse a dictionary word.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;catsandog&quot;, wordDict = [&quot;cats&quot;,&quot;dog&quot;,&quot;sand&quot;,&quot;and&quot;,&quot;cat&quot;]
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 300</code></li>
	<li><code>1 &lt;= wordDict.length &lt;= 1000</code></li>
	<li><code>1 &lt;= wordDict[i].length &lt;= 20</code></li>
	<li><code>s</code> and <code>wordDict[i]</code> consist of only lowercase English letters.</li>
	<li>All the strings of <code>wordDict</code> are <strong>unique</strong>.</li>
</ul>

class TrieNode{

    public :

    TrieNode* children[26];

    bool end_of_word;

    TrieNode(){

        for (int idx = 0 ; idx < 26 ; idx ++){

            this -> children[idx] = nullptr;

        }

        this -> end_of_word = false;

    }

};

class Solution {
public:
    
    void insert (TrieNode* root, string s){

        TrieNode* curr = root;

        for (int jdx = 0 ; jdx < s.size() ; jdx ++){

            char ch = s[jdx];

            TrieNode* next = (curr -> children[ch - 'a'] == nullptr) ? new TrieNode() : curr -> children[ch-'a'];

            curr = curr -> children[ch - 'a'] = next;
        }

        curr -> end_of_word = true;

    } 

    bool search(TrieNode* root,string word) {
        
        TrieNode* curr = root;

        for (int idx = 0 ; idx < word.size() ; idx ++){

            char ch = word[idx];

            if (curr -> children[ch - 'a'] == nullptr){
                return false;
            }

            curr = curr->children[ch-'a'];
        }

        return curr->end_of_word;

    }

    bool partition(TrieNode* root,int start,string word,vector <int>& dp){

        if (dp[start] != -1){
            return dp[start];
        }

        for (int idx = start+1 ; idx <= word.size() ; idx++){

            if (search(root,word.substr(start,idx-start)) && partition(root,idx,word,dp)){
                dp[start] = 1;
                return true;
            }

        }

        return dp[start] = 0;

    }

    bool wordBreak(string s, vector<string>& wordDict) {
        
        TrieNode* root = new TrieNode();

        vector <int> dp(s.size()+1,-1);

        dp[s.size()] = 1;

        for (int idx = 0 ; idx < wordDict.size() ; idx ++){

            insert(root,wordDict[idx]);

        }

        return partition(root,0,s,dp);

    }
};
20751