79.Word Search

Tags: Array Medium Backtracking

Links: https://leetcode.com/problems/word-search/

---

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

---

class Solution {
    string res;
    int direction[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    vector<vector<bool>> used;
    int m, n, len;
public:
    bool exist(vector<vector<char>>& board, string word) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        m = board.size(); if (m == 0) return false;
        n = board[0].size();
        used.resize(m);
        for (int i = 0; i < m; ++i) used[i].resize(n, false);

        int pos = 0; len = word.size();
        res.resize(len);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!used[i][j] && board[i][j] == word[pos]) {
                    res[pos] = word[pos];
                    DFS(i, j, board, word, pos + 1);
                    if (res == word) return true;
                    init(used);
                }
            }
        }

        return false;
    }

    void DFS(int row, int col, const vector<vector<char>>& board, const string & word, int pos)
    {
        used[row][col] = true;
        for (int i = 0; i < 4; ++i) {
            int nextRow = row + direction[i][0];
            int nextCol = col + direction[i][1];
            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && pos < len 
                && !used[nextRow][nextCol] && board[nextRow][nextCol] == word[pos]) {
                res[pos] = word[pos];
                if (res == word) return; //剪枝，已经找到答案就不需要再搜索
                DFS(nextRow, nextCol, board, word, pos + 1);
                used[nextRow][nextCol] = false; //恢复被搜索过但是不能构成word的区域
            }
        }

    }

    void init(vector<vector<bool>>& used)
    {
        fill(res.begin(), res.end(), ' ');
        for (auto & e : used) fill(e.begin(), e.end(), false);
    }
};

这道题目其实思路很直接，找到第一个和word首字母相同的位置开始搜索，用pos记录在word匹配的位置，这里有两个关键点，第一次写的时候忽略了。

第一个是要在搜索中要记得恢复被搜过的区域，也就是used[nextRow][nextCol] = false;，比如矩阵为：

A B C E
S F E S
A D E E
word = ABCESEEEFS

如果不恢复被搜索过的区域，就会造成这个测试用例过不去，因为很可能到C的时候不是向右搜索而是向下，那么不能得到正确的答案，回退的时候发现其他字母都被用过了，于是造成搜索失败。

第二个是要剪枝，在倒数第三个测试用例的时候TLE了，考虑ba...a，中间有很多a，矩阵里只有最后一个字母是b，其他全是a的情况，其实就是避免无谓的搜索，如果已经找到了正确答案，那就直接返回即可。