<p>You are given a <strong>0-indexed</strong> string <code>s</code> and a dictionary of words <code>dictionary</code>. You have to break <code>s</code> into one or more <strong>non-overlapping</strong> substrings such that each substring is present in <code>dictionary</code>. There may be some <strong>extra characters</strong> in <code>s</code> which are not present in any of the substrings.</p>

<p>Return <em>the <strong>minimum</strong> number of extra characters left over if you break up </em><code>s</code><em> optimally.</em></p>

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

<pre>
<strong>Input:</strong> s = &quot;leetscode&quot;, dictionary = [&quot;leet&quot;,&quot;code&quot;,&quot;leetcode&quot;]
<strong>Output:</strong> 1
<strong>Explanation:</strong> We can break s in two substrings: &quot;leet&quot; from index 0 to 3 and &quot;code&quot; from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

</pre>

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

<pre>
<strong>Input:</strong> s = &quot;sayhelloworld&quot;, dictionary = [&quot;hello&quot;,&quot;world&quot;]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can break s in two substrings: &quot;hello&quot; from index 3 to 7 and &quot;world&quot; from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.
</pre>

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

<ul>
	<li><code>1 &lt;= s.length &lt;= 50</code></li>
	<li><code>1 &lt;= dictionary.length &lt;= 50</code></li>
	<li><code>1 &lt;= dictionary[i].length &lt;= 50</code></li>
	<li><code>dictionary[i]</code>&nbsp;and <code>s</code> consists of only lowercase English letters</li>
	<li><code>dictionary</code> contains distinct words</li>
</ul>

/*
    Backtracking:
    At any index i, we can potentially break the word there,
    or add to our current substring (to break in the future)
    -   We can only break at this current point if our substring is in dictionary
    -   We can always add to our current substring, until we exhaust all characters
        in s.

    Therefore:
    1.  Find the min waste if we can break at the current index.
    2.  Find the min waste if we decide to add to our current substring.
    3.  Return the min between the two.

    Tabulation:
    dp[i] is defined as the min waste breaking s[0:i] optimally.
    -   Base case: dp[0] is trivially 0, as there's no waste with an empty string.
    -   Step case: at index i, either we could've used a word to reduce waste here, or not.
        >   If we can't use a word, skip = dp[i - 1] + 1.
        >   If we can, take = min(dp[i - len(word)]).
        >   dp[i] = min(take, skip)
    -   return dp[s.size() - 1]
*/

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isWord;
};

class Trie {
public:
    TrieNode* root;
    Trie() {
        root = new TrieNode();
    }

    void addWord(string s) {
        TrieNode* iter = root;
        for (char c : s) {
            if (!iter->children[c]) {
                iter->children[c] = new TrieNode();
            }
            iter = iter->children[c];
        }

        iter->isWord = true;
    }

    void addMany(vector<string> words) {
        for (string& word : words) {
            addWord(word);
        }
    }
};

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        Trie* trie = new Trie();
        trie->addMany(dictionary);
        
        for (int i = n - 1; i >= 0; i--) {
            int skip = dp[i + 1] + 1;
            int take = INT_MAX;

            TrieNode* iter = trie->root;
            for (int j = i; j < n; j++) {
                if (!iter->children.count(s[j])) {
                    break;
                }
                iter = iter->children[s[j]];
                if (iter->isWord) {
                    take = min(take, dp[j + 1]);
                }
            }
            dp[i] = min(skip, take);
        }

        return dp[0];
    }

    int solve(string curr, int waste, vector<string>& words, unordered_map<string, vector<int>>& dp) {
        if (curr.empty()) {
            return waste;
        }
        else if (dp.count(curr) && dp[curr][waste] != -1) {
            return dp[curr][waste];
        }

        int take = INT_MAX;
        for (string word : words) {
            if (curr.size() < word.size()) continue;

            string slice = curr.substr(0, word.size());
            if (slice == word) {
                take = min(take, solve(curr.substr(word.size()), waste, words, dp));
            }
        }

        int skip = solve(curr.substr(1), waste + 1, words, dp);

        int ans = min(take, skip);

        if (!dp.count(curr)) {
            dp[curr] = vector<int>(51, -1);
        }
        dp[curr][waste] = ans;

        return ans;
    }
};
106876