Skip to main content

Word Search II

Question​

Given a matrix of letters and a list of words, find all words in the matrix that are present in the list.

Example 1
Input: board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Solution​

all//Word Search II.py


def findWords(board, words):
    res = []
    trie = {}
    for w in words:
        t = trie
        for c in w:
            if c not in t:
                t[c] = {}
            t = t[c]
        t['#'] = '#'
    for i in range(len(board)):
        for j in range(len(board[0])):
            dfs(board, i, j, trie, '', res)
    return res


def dfs(board, i, j, trie, path, res):
    if '#' in trie:
        res.append(path)
    if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
        return
    tmp = board[i][j]
    if tmp not in trie:
        return
    board[i][j] = "#"
    dfs(board, i+1, j, trie[tmp], path+tmp, res)
    dfs(board, i-1, j, trie[tmp], path+tmp, res)
    dfs(board, i, j+1, trie[tmp], path+tmp, res)
    dfs(board, i, j-1, trie[tmp], path+tmp, res)
    board[i][j] = tmp