# 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.

Example:

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

Output: ["eat","oath"]

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

# Solution

Approach 1: put words in a trie, and do dfs on each letter on the board.

# Code (Python)

Approach 1:

class TrieNode:
    
    def __init__(self):
        self.is_word = False
        self.children = {} # can also use an array of 26 chars

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, word: 'str') -> 'None':
        """
        Inserts a word into the trie.
        """
        cur = self.root
        for char in word:
            if char not in cur.children:
                cur.children[char] = TrieNode()
            cur = cur.children[char]
        cur.is_word = True

class Solution:
    # Why use a trie? For a single word, we're doing dfs starting with each letter on the board, looking letter by letter for a match. Without a trie, that takes W * O(N^2) dfsearches, and during each search we lose the chance to match a neighbor with potentially another word in the list. A trie bundles words together by the same prefix, so we can search for all words with the same prefix at once.
    def findWords(self, board: 'List[List[str]]', words: 'List[str]') -> 'List[str]':
        trie = Trie()
        for word in words:
            trie.insert(word)
        result = []
        for h in range(len(board)):
            for w in range(len(board[0])):
                self._search(h, w, board, trie.root, [], result)
        return result
    
    def _search(self, h, w, board, trie_node, so_far, result):
        letter = board[h][w] 
        if letter in trie_node.children:
            # mark as visited to avoid using the same letter on the board
            board[h][w] = '&'
            so_far.append(letter)
            if trie_node.children[letter].is_word:
                result.append(''.join(so_far))
                # delete the word from the pool for result deduplication
                trie_node.children[letter].is_word = False
            for delta_h, delta_w in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if 0 <= h + delta_h < len(board) and 0 <= w + delta_w < len(board[0]):
                    self._search(h + delta_h, w + delta_w, board, trie_node.children[letter], so_far, result)
            so_far.pop()
            board[h][w] = letter

# Code (C++)

Approach 1:

class Solution {
    struct TrieNode {
        TrieNode *children[26];
        bool visited;
        int wordIdx;
        TrieNode() : visited(false), wordIdx(-1) {
            for (int i = 0; i < 26; ++i)
                children[i] = NULL;
        }
    };
private:
    vector<string> res;
    void addWord(TrieNode *root, string word, int wordIdx) {
        TrieNode *node = root;
        for (int i = 0; i < word.size(); ++i)
        {
            int letter = word[i] - 'a';
            if (!node->children[letter])
            {
                node->children[letter] = new TrieNode();
            }
            node = node->children[letter];
        }
        node->wordIdx = wordIdx;
    }
    void doFindWords(vector<vector<char>>& board, int row, int col, vector<vector<bool>>& visited, vector<string>& words, TrieNode *root) {
        int letter = board[row][col] - 'a';
        TrieNode *next = root->children[letter];
        if (!next || visited[row][col])
            return;
        if (next->wordIdx >= 0 && !next->visited)
        {
            res.push_back(words[next->wordIdx]);
            next->visited = true;
        }
        visited[row][col] = true;
        if (row > 0)
            doFindWords(board, row-1, col, visited, words, next);
        if (row < board.size()-1)
            doFindWords(board, row+1, col, visited, words, next);
        if (col > 0)
            doFindWords(board, row, col-1, visited, words, next);
        if (col < board[0].size()-1)
            doFindWords(board, row, col+1, visited, words, next);
        visited[row][col] = false;
    }
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        int m = board.size();
        int n = board[0].size();
        TrieNode root;
        for (int i = 0; i < words.size(); ++i)
        {
            addWord(&root, words[i], i);
        }
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                doFindWords(board, i, j, visited, words, &root);
            }
        }
        return res;
    }
};