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

One of the efficient ways to solve this problem is to use Trie. For more details please look https://en.wikipedia.org/wiki/Trie. In two words, it is a special data structure, similar to trees, but which has letters inside and used to quick search of patterns in strings. For implementation of Trie, please visit problem 208. Implement Trie (however I put my code here as well)

Outline of algorithm:

  1. For each word in our words insert it in our Trie.
  2. Starting with each symbol in our board, start dfs (backtracking) which are looking for words in our Trie.

Variables: self.num_words is total number of words we still need to find, in the beginning it is equal to total number of words. res is our result, where we keep found words. trie is our trie.

Now, how our dfs(self, board, node, i, j, path, res) works?

  1. board is our original board, node is current node of trie, i and j are current coordinates we are it, path is word build so far and res is global variable for found words.
  2. First, we check if we still need to look for words, if not, return
  3. Check if the node we are in currently is end_node: it means, that some word was found! We add it to our res, mark node.end_node as False (we do not want to search it once again) and decrease number of words we still need to find by 1.
  4. If we out of border or we inside border, but we can not traverse our trie we again do nothing.
  5. Now, we mark (i,j) position in our board as visited: #, call our dfs for all neibours, and then restore value ofr (i,j) position. (the reason is in pyton if we give list as parameter of recursive method, it will deal as global variable, so we need to fix it when we returned from our recursion).

Complexity. This is difficult question, space complexity is needed to keep our trie, which is O(k), where k is sum of length of all words. Time complexity is O(mn*3^T), where m and n are sizes of our board and T is the length of the longest word in words. Why? Because we start our dfs from all points of our board and do not stop until we make sure that the longest word is checked: if we are not lucky and this word can not be found on board we need to check potentialy to the length T. Why 3^T? Because each time we can choose one of three directions, except the one we came from.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        root = self.root
        for symbol in word:
            root = root.children.setdefault(symbol, TrieNode())
        root.end_node = 1

class Solution:
    def findWords(self, board, words):
        self.num_words = len(words)
        res, trie = [], Trie()
        for word in words: trie.insert(word) 

        for i in range(len(board)):
            for j in range(len(board[0])):
                self.dfs(board, trie.root, i, j, "", res)
        return res

    def dfs(self, board, node, i, j, path, res):
        if self.num_words == 0: return

        if node.end_node:
            res.append(path)
            node.end_node = False
            self.num_words -= 1

        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]): return 
        tmp = board[i][j]
        if tmp not in node.children: return

        board[i][j] = "#"
        for x,y in [[0,-1], [0,1], [1,0], [-1,0]]:
            self.dfs(board, node.children[tmp], i+x, j+y, path+tmp, res)
        board[i][j] = tmp

If you like the solution, you can upvote it on leetcode discussion section: Problem 0212