<p>Design a data structure that is initialized with a list of <strong>different</strong> words. Provided a string, you should determine if you can change exactly one character in this string to match any word in the data structure.</p>

<p>Implement the&nbsp;<code>MagicDictionary</code>&nbsp;class:</p>

<ul>
	<li><code>MagicDictionary()</code>&nbsp;Initializes the object.</li>
	<li><code>void buildDict(String[]&nbsp;dictionary)</code>&nbsp;Sets the data structure&nbsp;with an array of distinct strings <code>dictionary</code>.</li>
	<li><code>bool search(String searchWord)</code> Returns <code>true</code> if you can change <strong>exactly one character</strong> in <code>searchWord</code> to match any string in the data structure, otherwise returns <code>false</code>.</li>
</ul>

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

<pre>
<strong>Input</strong>
[&quot;MagicDictionary&quot;, &quot;buildDict&quot;, &quot;search&quot;, &quot;search&quot;, &quot;search&quot;, &quot;search&quot;]
[[], [[&quot;hello&quot;, &quot;leetcode&quot;]], [&quot;hello&quot;], [&quot;hhllo&quot;], [&quot;hell&quot;], [&quot;leetcoded&quot;]]
<strong>Output</strong>
[null, null, false, true, false, false]

<strong>Explanation</strong>
MagicDictionary magicDictionary = new MagicDictionary();
magicDictionary.buildDict([&quot;hello&quot;, &quot;leetcode&quot;]);
magicDictionary.search(&quot;hello&quot;); // return False
magicDictionary.search(&quot;hhllo&quot;); // We can change the second &#39;h&#39; to &#39;e&#39; to match &quot;hello&quot; so we return True
magicDictionary.search(&quot;hell&quot;); // return False
magicDictionary.search(&quot;leetcoded&quot;); // return False
</pre>

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

<ul>
	<li><code>1 &lt;=&nbsp;dictionary.length &lt;= 100</code></li>
	<li><code>1 &lt;=&nbsp;dictionary[i].length &lt;= 100</code></li>
	<li><code>dictionary[i]</code> consists of only lower-case English letters.</li>
	<li>All the strings in&nbsp;<code>dictionary</code>&nbsp;are <strong>distinct</strong>.</li>
	<li><code>1 &lt;=&nbsp;searchWord.length &lt;= 100</code></li>
	<li><code>searchWord</code>&nbsp;consists of only lower-case English letters.</li>
	<li><code>buildDict</code>&nbsp;will be called only once before <code>search</code>.</li>
	<li>At most <code>100</code> calls will be made to <code>search</code>.</li>
</ul>

"""
Magic Dictionary - Medium
20m

- build dict resets the data structure of strings
- search check if edit distance of string is 1 from any string

Solution 1:
- search will just iterate through all the strings and see if there is a diff of one
time: O(nm) n is # strings, m is avg length of string
space: O(nm) store all strings

Solution 2:
- edit distance: store data in a trie, and as we walk the trie, keep track of how many skips we did (allowed only one skip because edit distance of one)
time: O(m) length of given string
space: O(nm) store all strings in trie

must look at whole given string, optimal

hello
hhllo
cream

hhllo
cello
"""

from typing import List

class MagicDictionary:
    END_MARKER = "."

    def __init__(self):
        self.trie = {}

    def buildDict(self, dictionary: List[str]) -> None:
        for word in dictionary:
            cursor = self.trie
            for c in word:
                if c not in cursor:
                    cursor[c] = {}
                cursor = cursor[c]
            cursor[self.END_MARKER] = {}

    def search(self, searchWord: str) -> bool:
        cursor = self.trie

        def subSearch(searchWord, i, cursor, skipped):
            if i >= len(searchWord):
                return self.END_MARKER in cursor and skipped == 1

            c = searchWord[i]
            res = False
            # Backtrack for next characters
            for nextc in cursor:
                # If we need to skip a character
                if c != nextc:
                    # Can only skip one character max
                    if skipped >= 1:
                        continue
                    res = subSearch(searchWord, i + 1, cursor[nextc], skipped + 1)
                    if res:
                        return res
                # Don't need to skip a character
                else:
                    res = subSearch(searchWord, i + 1, cursor[nextc], skipped)
                    if res:
                        return res
            return False

        return subSearch(searchWord, 0, cursor, 0)


21500