212 Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example, Given words=["oath","pea","eat","rain"]and board=

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return

["eat","oath"]

Note: You may assume that all inputs are consist of lowercase lettersa-z.

The Idea: We can use a trie to navigate ourselves in the DFS traversal of the word matrix. Essentially, for every row and col of the matrix, we attempt a DFS. Within the DFS, we check for a few things to ensure that we are on the right path. 1) Rows and columns are within the bounds of the word matrix, 2) We are not stepping in an area we've visited already, 3) The current character of the board is within our trie. If all these succeed, then we can append the current word into our path, and attempt to descend down the the next direction in the matrix along with path that follows within the trie. If we successfully reach the end of the trie, this imply the DFS successful iterated through an entire word in the dictionary. At this point, we can append that path that forms the word into our results lists. One thing to keep in mind is the visited matrix remains independent per word in the input dictionary, because words can easily over lap. Therefore, it is necessary to mark each visited location back to not visited as the DFS backtracks.

Complexity: O(N^2) time where n is the total number of elements in the board. Justification: for i, j position on the matrix (N-elements), a DFS will at worst case, explore the entirety of the same matrix. O(2N) extra space for the recursive call which would reach the the number of elements in the matrix, and an additional N space for the visited matrix. One way to improve space complexity is to directly modify the element in the board to an non-alphabetical character as an indicator for being visited. When backtracking, mark it back to its original character.

import numpy as np


class Solution:
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """

        if not board:
            return [[]]

        def make_trie(words):
            trie = {}
            for word in words:
                iter_trie = trie
                for letter in word:
                    if letter not in iter_trie:
                        iter_trie[letter] = {}
                    iter_trie = iter_trie[letter]
                iter_trie['#'] = '#'
            return trie

        trie = make_trie(words)
        visited = np.zeros((len(board), len(board[0])))
        rotations = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        results = []

        def in_board(row, col):
            return row >= 0 and col >= 0 and row < len(board) and col < len(board[0])

        def dfs_find(row, col, trie, path):
            if '#' in trie:
                results.append(path)
            if not in_board(row, col) or visited[row][col] or board[row][col] not in trie:
                return
            else:
                target_c = board[row][col]
                visited[row][col] = 1
                for r, c in rotations:
                    dfs_find(row + r, col + c, trie[target_c], path + target_c)
                visited[row][col] = 0

        for i, row in enumerate(board):
            for j, char in enumerate(row):
                dfs_find(i, j, trie, '')

        return list(set(results))

board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

obj = Solution()
print(obj.findWords([["a"]], ["a"]))  # ["a"]
print(obj.findWords(board, ["oath", "pea", "eat", "rain"]))  # ["eat","oath"]
print(obj.findWords([["a","b"],["a","a"]], ["aba","baa","bab","aaab","aaa","aaaa","aaba"]))  # ["aaa","aaab","aaba","aba","baa"]