# 单词搜索 II

<p>给定一个 <code>m x n</code> 二维字符网格 <code>board</code><strong> </strong>和一个单词（字符串）列表 <code>words</code>，找出所有同时在二维网格和字典中出现的单词。</p>

<p>单词必须按照字母顺序，通过 <strong>相邻的单元格</strong> 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。</p>

<p> </p>

<p><strong>示例 1：</strong></p>
<img alt="" src="https://img-service.csdnimg.cn/img_convert/3c58915d280f9462e912c68fbe6cc128.jpeg" style="width: 322px; height: 322px;" />
<pre>
<strong>输入：</strong>board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
<strong>输出：</strong>["eat","oath"]
</pre>

<p><strong>示例 2：</strong></p>
<img alt="" src="https://img-service.csdnimg.cn/img_convert/2799340eb0a16624ef37341b8ab15fd9.jpeg" style="width: 162px; height: 162px;" />
<pre>
<strong>输入：</strong>board = [["a","b"],["c","d"]], words = ["abcb"]
<strong>输出：</strong>[]
</pre>

<p> </p>

<p><strong>提示：</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 <= m, n <= 12</code></li>
	<li><code>board[i][j]</code> 是一个小写英文字母</li>
	<li><code>1 <= words.length <= 3 * 10<sup>4</sup></code></li>
	<li><code>1 <= words[i].length <= 10</code></li>
	<li><code>words[i]</code> 由小写英文字母组成</li>
	<li><code>words</code> 中的所有字符串互不相同</li>
</ul>


## template

```cpp
#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    struct Node
    {
        bool isflag = false;
        Node *next[27] = {};
    };
    set<string> res;
    vector<string> ans;
    Node *root;
    vector<int> dirx{0, 0, 1, -1};
    vector<int> diry{1, -1, 0, 0};
    bool flag;

    void createtree(vector<string> &words)
    {
        root = new Node();

        for (auto w : words)
        {
            Node *p = root;
            for (int i = 0; i < w.length(); i++)
            {
                if (p->next[w[i] - 'a'] == NULL)
                {
                    p->next[w[i] - 'a'] = new Node();
                }
                p = p->next[w[i] - 'a'];
            }
            p->isflag = true;
        }
    }
    void backtrack(vector<vector<char>> &board, vector<vector<bool>> visited, int row, int col, Node *roott, string cur)
    {
        cur += board[row][col];
        roott = roott->next[board[row][col] - 'a'];
        if (!roott)
            return;
        if (roott->isflag == true)
        {

            res.insert(cur);
            flag = true;
        }
        visited[row][col] = true;

        for (int i = 0; i < 4; i++)
        {

            int nx = row + dirx[i];
            int ny = col + diry[i];
            if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board[0].size())
                continue;
            if (visited[nx][ny] == false)
            {
                backtrack(board, visited, nx, ny, roott, cur);
            }
        }
    }
    vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
    {

        if (board.size() == 0 || words.size() == 0)
            return ans;
        createtree(words);

        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[i].size(); j++)
            {
                Node *p = root;
                flag = false;
                if (p->next[board[i][j] - 'a'])
                {
                    vector<vector<bool>> visited{board.size(), vector<bool>(board[0].size(), false)};
                    backtrack(board, visited, i, j, p, "");
                }
            }
        }
        set<string>::iterator it;
        for (it = res.begin(); it != res.end(); it++)
            ans.push_back(*it);
        return ans;
    }
};


```

## 答案

```cpp

```

## 选项

### A

```cpp

```

### B

```cpp

```

### C

```cpp

```