<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 Solution {  
public:
    //O(N^3), spaceO(N)
    bool wordBreak(string s, vector<string>& wordDict) {
        int L = s.length();
        vector<int> dp(L + 1, 0);
        unordered_set<string> words_set(wordDict.begin(), wordDict.end());
        
        dp[L] = 1;
        
        for(int i = L - 1; i >= 0; i--){
            for(int j = i + 1; j <= L; j++){
                if(words_set.count(s.substr(i, j - i)) && dp[j] == 1){
                    dp[i] = 1;
                    break;
                }
            }
        }
        
        return dp[0];
        
    }
};
*/

/*
class Solution {  
public:
    //O(N^3), spaceO(N)
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words_set(wordDict.begin(), wordDict.end());
        int L = s.length();
        vector<int> dp(L + 1, 0);
        dp[0] = 1;
        
        for(int i = 1; i <= L; i++){
           for(int j = i; j > 0; j--){
               //Pay attention to indexes in substr and the s index is one behind
               if(words_set.count(s.substr(j - 1, i - j + 1)) && dp[j - 1]){
                   dp[i] = 1;
                   break;
               }
           } 
        }
        
        return dp[L];
    }    
};
*/
/*
class Solution {  
    vector<int> cache;
    
    bool isConcatinated(string& s, int istart, unordered_set<string>& words_set){
        if(istart == s.length()){
            return true;
        }
        
        if(cache[istart] != -1){
            return cache[istart];
        }
        
        bool result = 0;
        for(int i = istart; i < s.length(); i++){
            string cur_word = s.substr(istart, i - istart + 1);
            if(words_set.count(cur_word)){
                if(isConcatinated(s, i + 1, words_set)){
                    result = 1;
                    break;
                }
            }
        }
        
        cache[istart] = result;
        
        return result;
    }
    
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> words_set(wordDict.begin(), wordDict.end());
        cache.resize(s.length(), -1);
        
        return isConcatinated(s, 0, words_set);
    }
};
*/

// class Solution {
    
// public:
//     /*
//      bool wordBreak(string s, vector<string>& wordDict) {
//          set<string> table;
//          for(int i=0; i<wordDict.size(); i++){
//              table.insert(wordDict[i]);
//          }
//          queue<int> q;
//          int visited[s.length()];
//          for(int i=0 ; i< s.length(); i++){
//              visited[i]=0;
//          }
//          int start =0;
//          q.push(start);        
//          while(!q.empty()){
//              start = q.front();
//              q.pop();        
//              if(!visited[start]){
//                 for(int end = start+1; end<=s.length(); end++){
//                     if(table.count(s.substr(start,end-start))){
//                         q.push(end);
//                     if (end ==s.length()) return true; 
//                     }
//                 }
//              }
//              visited[start]=1;           
//          }
//          return false;        
//      }
//      */
    
//     //Time O(n^3) , Space O(n)
// public:
//     bool wordBreak(string s, vector<string>& wordDict) {
//         vector<int> checked (s.length(), -1);
        
//         unordered_set<string> table (wordDict.begin(), wordDict.end());
        
//         return find_words(s,0, table,checked);
//     }
    
//  private:  
//     bool find_words(string& s, int start, unordered_set<string>& table,
//                     vector<int>& checked){
//         if(start == s.length()) return true;
//         if(checked[start] != -1){
//             return checked[start];
//         }
        
//         int i =start;
//         string word = "";
//         while(i < s.length()){
//             word.append(1, s[start]);
//             if(table.count(word)){
//                 if(find_word(i + 1)){
//                     checked[i] = 1;
//                     return true;
//                 }
                    
//             }
//             i++;
//         }
//         checked[i] = 0;
//         return false;
        
//     }
    
    
    
    
//     bool find_words(string& s, int start, unordered_set<string>& table,
//                     vector<int>& checked){
//         if(start == s.length()) return true;
//         if(checked[start]!= -1) {
//             return checked[start];
//         }
        
//         string word = "";
//         // O(n)
//         for(int i=start; i<s.length(); i++){
//             //word += s[i]; ->This s O(n^2)
//             word.append(1, s[i]);
//             if(table.count(word) && find_words(s,i+1,table,checked)){
//                 checked[start]=1;
//                 return true;
//             }
//         }
//         checked[start]=0;
//         return false;
//     }
//    /* 
//     public:
//     struct Trie{
//         unordered_map<char, Trie*> children;
//         string word = "";
//     };
    
//     Trie *root;
//     bool wordBreak(string s, vector<string>& wordDict) {
//         vector<int> checked (s.length(), -1);
        
//         unordered_set<string> table (wordDict.begin(), wordDict.end());
//         root = new Trie();
//         Trie *t;
//         for(auto word : wordDict){
//             t = root;
//             for(char c : word){
//                 if(!t->children.count(c)){
//                     t->children[c] = new Trie();
//                 }
                
//                 t = t->children[c];
//             }
//         }
        
//         t = root;
//         for(int i = 0; i < s.length(); i++){
//             if(t->children.count[s[i]]){
//                 backtrack
//             }
//         }
        
        
//     }*/

// };

class Solution {  
    unordered_set<string> wordSet;
    vector<int> seen;
    bool findStrings(string& s, int start)
    {
        if(start == s.length())
        {
            return true;
        }

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

        string cur = "";
        for(int i = start; i < s.length(); i++)
        {
            cur.append(1, s[i]);
            if(wordSet.count(cur))
            {
                if(findStrings(s, i + 1))
                {
                    return seen[start] = true;
                }
            }
        }

        return seen[start] = false;
    }
public:
    //O(N^3), spaceO(N)
    bool wordBreak(string s, vector<string>& wordDict) {
        wordSet.insert(wordDict.begin(), wordDict.end());
        seen.resize(s.length(), -1);
        return findStrings(s, 0);
    }
};
11144