'''
Build a trie for the words in the dictionary.
Check each word in the query against the trie.
'''
class Solution:
def twoEditWords(self, queries: List[str], dictionary: List[str]) -> List[str]:
def addWordToTrie(trie, word):
for c in word:
if c not in trie:
trie[c] = dict()
trie = trie[c]
def checkWord(trie, word, numEdits, idx):
if idx == len(word) and numEdits >= 0:
return True
if numEdits < 0:
return False
for char, childTrie in trie.items():
newEdits = numEdits
if char != word[idx]:
newEdits -= 1
if checkWord(childTrie, word, newEdits, idx+1):
return True
return False
trie = dict()
res = []
for word in dictionary:
addWordToTrie(trie, word)
for word in queries:
if checkWord(trie, word, 2, 0):
res.append(word)
return res
