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

#if 1
    #define LOGGV(x) std::cout << "\n" << __LINE__ << " : " <<  #x << " = " << x
    #define LOGGVV(kk, ll) LOGGV(kk) << ", " <<  #ll << " = " << ll
    #define LOGGVVV(kk, ll, mm) LOGGVV(kk, ll) << ", " <<  #mm << " = " << mm
    #define LOGGVVVV(kk,ll, mm, nn) LOGGVVV(kk, ll, mm) << ", " <<  #nn << " = " << nn
    #define LOGGPAIR(em) std::cout << std::endl << __LINE__ << " : " << #em <<"[" << em.first << ", " << em.second << "]";

    #define LOGGPAIRS(path) \
            std::cout << std::endl << __LINE__ << " : " << #path << " = " << path.size() << " ["; \
            for (auto x : path) std::cout << "[" << x.first << ", " << x.second << "], "; \
            std::cout << "]"

    #define LOGGSIZE(path) \
            std::cout << std::endl << __LINE__ << " : " << #path << " = " << path.size()

    #define LOGGVECTOR(path) \
            std::cout << std::endl << __LINE__ << " : " << #path << " = " << path.size() << " ["; \
            for (auto x : path) std::cout << x << ", "; \
            std::cout << "]"

    #define LOGGIDX(path,i) std::cout << std::endl << __LINE__ << " : " << #path <<"[" << i << "]" << " = " << path[i];

    #define LOGGLINE std::cout << std::endl << __LINE__ << " : "

    #define LOGGNODE(em) LOGLINE << #em << " = " << em->val

    static long LOGGMANY = 0;
#else
    #define LOGGV(x)
    #define LOGGVV(kk, ll)
    #define LOGGVVV(kk, ll, mm)
    #define LOGGVVVV(kk, ll, mm, nn)
    #define LOGGPAIRS(path) 
    #define LOGGPAIR(em)
    #define LOGGSIZE(path)
    #define LOGGVECTOR(path)
    #define LOGGIDX(path,i)
    #define LOGGLINE
    #define LOGGNODE(em)
#endif

class Solution {
public:
#if 1
// DP
    bool wordBreak(string s, vector<string>& wordDict) {
        int sLen = s.length();
        vector<bool> match(sLen, false);
        match.push_back(true);

        for (int i = match.size() - 2; i >= 0; i--) {
            LOGGV(i);
            LOGGVECTOR(match);
            for (auto word : wordDict) {
                if (word == s.substr(i, word.length())) {
                    match[i] = match[i + word.length()];
                    if (match[i]) break;
                }
            }
        }

        return match[0];
    }
#else
// Iterative - TLE
    bool wordBreak(string s, vector<string>& wordDict) {
        if (s.length() == 0) return true;

        for (auto word : wordDict) {
            string cand = s.substr(0, word.length());
            // LOGGVVV(s, word, cand);
            if (cand == word) {
                string newS = s.substr(word.length(), s.length() - word.length());
                if (wordBreak(newS, wordDict)) return true;
            }
        }
        return false;
    }
#endif
};
10458