# 212. Word Search II
#### Difficulty: Hard
link: https://leetcode.com/problems/word-search-ii/

### 1. Backtracking + Trie
~~#### $O(1)$ runtime, $O(1)$ space~~

相較於前一題[79. Word Search](https://leetcode.com/problems/word-search/)，需要檢查的word變多了，如果直接沿用前一題的演算法，一個個word去搜尋會很沒效率，這是可以優化的地方。

希望優化的方向是，同樣跑一次全board的search，但backtracking函數能檢查到每個word。

最簡單的方式是，每次函數都O(k)掃過每個word檢查，但這樣可能會太慢。希望能只檢查走到目前為止還相符的word，而且排除掉已經成功找到過的word，能滿足這樣需求的資料結構就是Trie。

dfs用iterative的做法會比recursive還要快。

##### python

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.is_word = False
        self.count = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        node.count += 1
        for char in word:
            node = node.children[char]
            node.count += 1
        node.is_word = True
    
    def remove(self, word):
        node = self.root
        node.count -= 1
        for char in word:
            pre_node = node
            node = node.children[char]
            node.count -= 1
            if node.count == 0:
                del pre_node.children[char]
        node.is_word = False

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trie = Trie()
        board_cnt = Counter([ch for row in board for ch in row])
        for word in words:
            word_cnt = Counter(word)
            # optimization
            if any(word_cnt[ch] > board_cnt[ch] for ch in word_cnt):
                continue
            trie.insert(word)
        
        result = []
        m, n = len(board), len(board[0]) 
        def dfs(x, y, path, node):
            if node.is_word:
                result.append(path)
                trie.remove(path)
                
            board[x][y] = "#"
            for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
                if 0 <= nx < m and 0 <= ny < n:
                    next_step = board[nx][ny]
                    if next_step in node.children:
                        dfs(nx, ny, path + next_step, node.children[next_step])
            board[x][y] = path[-1]
        
        for i in range(m):
            for j in range(n):
                char = board[i][j]
                if char in trie.root.children:
                    dfs(i, j, char, trie.root.children[char])
        
        return result

###### tags: `leetcode`