LeetCode79. Word Search（递归 / 回溯）

Medium
Accepted：266,924
Submissions：866,035

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.

链接

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

题意

给定一个二维平面的字母和一个单词，判断单词是否存在该平面中。一个字符可由相邻顺序的字母构造，相邻指上下相邻和左右相邻。

题解

实际上就是在一个二维字符数组中进行搜索，对于当前字母，有四个可选择的方向，递归下去，看能否和单词完全匹配。

注意递归回溯时，需要把之前访问过的标记取消。

代码

class Solution {
private:
    int n, m;
    int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    vector <vector <bool> > vis;
    bool check(int x, int y)
    {
        return x >= 0 && x < n && y >= 0 && y < m && !vis[x][y];
    }
    bool solve(const vector<vector<char>>& board, const string & word, int index,
            int startx, int starty)
    {
        if (index == word.size() - 1) // 最后一个字母
            return board[startx][starty] == word[index];
        if (board[startx][starty] == word[index]) // 当前匹配
        {
            vis[startx][starty] = true;
            for (int i = 0; i < 4; ++i) // 四个方向
            {
                int newx = startx + dir[i][0];
                int newy = starty + dir[i][1];
                if (check(newx, newy))
                {
                    if (solve(board, word, index + 1, newx, newy))
                        return true;
                }
            }
            vis[startx][starty] = false; // 回溯
        }
        return false; // 未找到
    }

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

The end.
2019年4月13日星期六