> For the complete documentation index, see [llms.txt](https://garylai.gitbook.io/algorithm-and-data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garylai.gitbook.io/algorithm-and-data-structure/problems/backtrack/word-search/word-search-ii.md).

# 212. Word Search II

[212. Word Search II](https://leetcode.com/problems/word-search-ii/)

這一題是 [79. Word Search](/algorithm-and-data-structure/problems/backtrack/word-search.md) 的進階版，原先我們要找的是給定一個字串，看這個一個字串是否存在，這題是給定很多字串，要看哪些字串存在？

第一個直覺的想法是，那就把第一題的解法把字串一個一個檢查就好，但是這樣的方法很明顯會超時。

```python
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        rows = len(board)
        cols = len(board[0])
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        def backtrack(r, c, word):
            if len(word) == 0:
                return True
            if 0 <= r < rows and 0 <= c < cols and board[r][c] == word[0]:
                board[r][c] = '#'
                for dr, dc in directions:
                    if backtrack(r+dr, c+dc, word[1:]):
                        board[r][c] = word[0]
                        return True
                board[r][c] = word[0]
            return False
        ans = set()

        for word in set(words):
            for r in range(rows):
                for c in range(cols):
                    if backtrack(r, c, word):
                        ans.add(word)
        return ans
```

## Trie

這個解法其實滿特別的，我依稀有想到，但是實作的細節還是有點難，LeetCode 上面是直接寫出了解答，但是我覺得如何去思考出這個想法才是最困難的。

其實上面的暴力解，其實我們已經做了很多剪枝的動作，但是是一個字串一個字串開始搜尋，如果說今天有兩個字串，`abcdef` 和`abcdeg` 在上面的那個做法就會很浪費時間，因為在 `abcdef` 時，我們就已經知道了 `abcde` 的存在，只差一步之遙，就可以找到 `g` 了。**只要附近還有節點沒有搜索過，是不是就應該要再加油一點去看看？**

想到了這裡，其實方向很像是動態規劃，我甚至覺得這也算是動態規劃的一種變形？以這個例子來說，我們要是在搜尋的時候可以一起搜尋類似的字串，那這樣不是很好嗎？這個題目困難在是否可以一直想到這一步，因為要搜尋類似的字串，就可以想到就會需要使用 `Trie` 。

第一個步驟就是，把我們想要搜尋的字串先轉換成 Trie ，**並且要在結尾處標記是哪個單字**，方便之後直接找出結果。

接下來依然是回朔法，但是我們透過 Trie 可以更大量的減少搜索空間

### 第一步

在遍歷矩陣時，要先注意矩陣的元素是否是在 Trie 的根節點？如果沒有的話，代表從那個點出發一定不會有我們目標的字串

### 第二步

先取得該節點，如果該節點有 Trie 的結束標記符號，代表我們找到了目標字串之一，加到答案裡面。

### 第三步

開始向下探索，要確定三件事情

1. 是否在邊界裡面？
2. 有沒有在目前 Trie Node 的子節點裡面？
3. 是否有造訪過？

回溯方法基本就結束了

```python
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        rows = len(board)
        cols = len(board[0])
        directions = [(1,0),(0,1),(-1,0),(0,-1)]
        trie = {}

        for word in words:
            node = trie
            for char in word:
                node = node.setdefault(char, {})
            node['$'] = word
        ans = set()

        def backtrack(row, col, visited, root):
            node = root[board[row][col]]
            if '$' in node.keys():
                ans.add(node['$'])
            visited.add((row, col))
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] in node and (nr, nc) not in visited:
                    backtrack(nr, nc, visited, node)
            visited.remove((row, col))

        for row in range(rows):
            for col in range(cols):
                if board[row][col] in trie:
                    backtrack(row, col, set(), trie)
        return ans
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://garylai.gitbook.io/algorithm-and-data-structure/problems/backtrack/word-search/word-search-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.