Word Search II

gistfile1.txt

# https://leetcode.com/problems/word-search-ii/

def makeTrie():
    newTrie = {}
    return newTrie
    
def addWord(word, trie):
    currentTrie = trie
    for letter in word:
        if not letter in currentTrie:
            newTrie = makeTrie()
            currentTrie[letter] = newTrie
        currentTrie = currentTrie[letter]
    currentTrie['$'] = word
    
def doSearch(board, m, n, words):
    trie = makeTrie()
    for word in words:
        addWord(word, trie)
    used = [[False for j in range(n)] for i in range(m)]
    found = []
    if '$' in trie:
        found.append(trie['$'])
    for i in range(m):
        for j in range(n):
            doSearchRec(board, m, n, trie, used, found, i, j)
    return list(set(found))
    
def doSearchRec(board, m, n, trie, used, found, i, j):
    letter = board[i][j]
    if letter in trie:
        subTrie = trie[letter]
        if '$' in subTrie:
            found.append(subTrie['$'])
        used[i][j] = True
        if i > 0 and not used[i - 1][j]:
            doSearchRec(board, m, n, subTrie, used, found, i - 1, j)
        if i + 1 < m and not used[i + 1][j]:
            doSearchRec(board, m, n, subTrie, used, found, i + 1, j)
        if j > 0 and not used[i][j - 1]:
            doSearchRec(board, m, n, subTrie, used, found, i, j - 1)
        if j + 1 < n and not used[i][j + 1]:
            doSearchRec(board, m, n, subTrie, used, found, i, j + 1)
        used[i][j] = False

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        if not board:
            return []
        if not board[0]:
            return []
        m = len(board)
        n = len(board[0])
        return doSearch(board, m, n, words)