题目描述

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

解法

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (search(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }

    bool search(vector<vector<char>>& board, string word, int index, int i, int j) {
        if (word.size() == index) return true; //递归跳出：匹配到字符串结尾了，才返回true
        int m = board.size(), n = board[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || word[index] != board[i][j]) return false; //递归跳出: 中途匹配失败
        // 中途匹配成功，继续递归
        char c = board[i][j];
        board[i][j] = '#';
        bool res = search(board, word, index + 1, i, j - 1)
                || search(board, word, index + 1, i, j + 1)
                || search(board, word, index + 1, i - 1, j)
                || search(board, word, index + 1, i + 1, j);
        board[i][j] = c; //恢复现场
        return res;
        
    } 
};

思路

这道题就是典型的深度优先搜索(dfs)。
board中每个元素都可能作为深搜的起点，所以最大可能要深搜m*n次。见exist函数里的for循环。
每次的深搜，是search函数。
以board[i][j]作为起点的字符串匹配为例，说一下这个匹配（深搜）的过程：
起点：board[i][j], word[0]。
如果这俩字符相等，那么return board[i][j]上下左右4个相邻字符是否有和word[1]相等的，只要有一个相等的，那么返回true。这个过程是递归的。

• 递归退出的条件：
  1） true: 匹配到字符串结尾了，深搜结束。
  2）false: 这俩字符不相等，或者board[i][j]越界。（上下左右递归的过程可能越界）
• 深搜的过程中有个限制条件，每个格子只能走一次，走过的不能重复走，所以可以用visited标记数组记录当前格子是否在走过了，或者走过一个格子用'#'销毁一个格子来避免重复。注意这个格子在深搜的过程中被改变了，因此深搜完了还要恢复现场。因为最多可能深搜m*n次，不要对以别的起点的深搜造成影响。