solution.md

# 单词搜索

<p>给定一个 <code>m x n</code> 二维字符网格 <code>board</code> 和一个字符串单词 <code>word</code> 。如果 <code>word</code> 存在于网格中，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p><p>单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0079.Word%20Search/images/word2.jpg" style="width: 322px; height: 242px;" /><pre><strong>输入：</strong>board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"<strong><br />输出：</strong>true</pre><p><strong>示例 2：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0079.Word%20Search/images/word-1.jpg" style="width: 322px; height: 242px;" /><pre><strong>输入：</strong>board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"<strong><br />输出：</strong>true</pre><p><strong>示例 3：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0079.Word%20Search/images/word3.jpg" style="width: 322px; height: 242px;" /><pre><strong>输入：</strong>board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"<strong><br />输出：</strong>false</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 <= 6</code></li>	<li><code>1 <= word.length <= 15</code></li>	<li><code>board</code> 和 <code>word</code> 仅由大小写英文字母组成</li></ul><p> </p><p><strong>进阶：</strong>你可以使用搜索剪枝的技术来优化解决方案，使其在 <code>board</code> 更大的情况下可以更快解决问题？</p>
<p>以下错误的选项是？</p>

## aop

### before

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

```cpp
int main()
{
    Solution sol;
    int a = 3, b = 4;
    vector<vector<char>> board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
    string word = "ABCCED";

    bool res;
    res = sol.exist(board, word);
    cout << res;
    return 0;
}
```

## 答案

```cpp
class Solution
{
public:
    vector<vector<int>> dirs{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    bool exist(vector<vector<char>> &board, string word)
    {
        int n = board.size(), m = board[0].size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (dfs(board, word, 0, i, j))
                    return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>> &board, string &word, int idx, int x, int y)
    {
        if (board[x][y] != word[idx])
            return false;
        if (idx == word.size() - 1)
            return true;

        char tmp = board[x][y];
        board[x][y] = 0;
        for (const auto &dir : dirs)
        {
            if (x + dir[0] < 0 || x + dir[0] >= board.size() || y + dir[1] < 0 || y + dir[1] >= board[0].size())
                continue;
            if (dfs(board, word, idx, x + dir[0], y + dir[1]))
                return true;
        }
        board[x][y] = tmp;
        return false;
    }
};
```
## 选项


### A

```cpp
class Solution
{
public:
    bool search(vector<vector<char>> &board, string word, int i, int j, int pos)
    {
        if (pos == word.size())
            return true;
        if (i < 0 || j < 0 || i >= board.size() || j >= board[i].size())
            return false;
        if (word[pos] != board[i][j])
            return false;
        char temp = board[i][j];
        board[i][j] = '.';
        bool result = search(board, word, i + 1, j, pos + 1) || search(board, word, i - 1, j, pos + 1) || search(board, word, i, j - 1, pos + 1) || search(board, word, i, j + 1, pos + 1);
        board[i][j] = temp;
        return result;
    }

    bool exist(vector<vector<char>> &board, string word)
    {
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board[i].size(); j++)
                if (search(board, word, i, j, 0))
                    return true;
        return false;
    }
};
```

### B

```cpp
class Solution
{
public:
    bool exist(vector<vector<char>> &board, string word)
    {
        rows = board.size(), columns = board[0].size();
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < columns; j++)
            {
                if (backtrack(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }

private:
    int rows, columns;
    bool backtrack(vector<vector<char>> &board, string &word, int x, int y, int index)
    {

        if (x >= rows || x < 0 || y >= columns || y < 0 || board[x][y] != word[index])
        {
            return false;
        }

        if (index == word.size() - 1)
        {
            return true;
        }

        board[x][y] = ' ';

        if (backtrack(board, word, x - 1, y, index + 1) || backtrack(board, word, x + 1, y, index + 1) || backtrack(board, word, x, y - 1, index + 1) || backtrack(board, word, x, y + 1, index + 1))
        {
            return true;
        }

        board[x][y] = word[index];
        return false;
    }
};
```

### C

```cpp
class Solution
{
public:
    bool DFS(vector<vector<char>> &board, string word, int row, int col, int index, vector<vector<int>> &flag)
    {
        if (index == word.length())
        {
            return true;
        }
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] != word[index])
        {
            return false;
        }
        if (0 == flag[row][col])
        {
            flag[row][col] = 1;
            if (DFS(board, word, row - 1, col, index + 1, flag))
            {
                return true;
            }
            if (DFS(board, word, row + 1, col, index + 1, flag))
            {
                return true;
            }
            if (DFS(board, word, row, col - 1, index + 1, flag))
            {
                return true;
            }
            if (DFS(board, word, row, col + 1, index + 1, flag))
            {
                return true;
            }
            flag[row][col] = 0;
        }
        return false;
    }
    bool exist(vector<vector<char>> &board, string word)
    {
        int m = board.size();
        int n = board[0].size();
        int k = word.length();
        vector<vector<int>> flag(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (DFS(board, word, i, j, 0, flag))
                {
                    return true;
                }
            }
        }
        return false;
    }
};
```