Leetcode|Leetcode:79. 单词搜索 Leetcode|C

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:

board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ]给定 word = "ABCCED", 返回 true. 给定 word = "SEE", 返回 true. 给定 word = "ABCB", 返回 false.

解题思路：
组合问题一看就是DFS能搞出来，搞出来容易关键在于尽可能避免无用的搜索。基本思路就是遍历字符数组，若果单词的第一个字符与当前位置的字符相等，哪就从这个地方开始搜索，接着在邻居找单词的下一个字符，很显然需要递归，因为单词长度未知。
1. 当邻居没有找到下一个字符，结束本次搜索。
2. 注意一次深搜不能往回走，一开始设置了VISIT数组来记录，发现每次搜索完都要更新VISIT，速度极慢。本题的特点是单词中肯定是没有空格的，也就意味着可以将访问过的元素变成空格，即可避免VISIT。
3. 迭代的次数就决定了当前层数是否能够找到单词，如果迭代了5次，而单词的长度也是5，那么就可以返回true,一开始每一迭代一次都记录当前找到的字符串，速度就慢了。

文章图片

C++代码
class Solution{ public: bool exist(vector>& board, string word) { if (word == "") return true; _word = word; m = board.size(), n = board[0].size(); if (m == 0 \|\| n == 0) return false; data = https://www.it610.com/article/board; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (board[i - 1][j - 1] == word[0]&& DFS(i, j, 0)) { return true; } } } return false; } private: bool DFS(int i, int j, int pos) { if (_word[pos] == data[i - 1][j - 1]) { char c = data[i - 1][j - 1]; data[i - 1][j - 1] = ' '; if (pos == int(_word.size())-1) return true; else { if (i > 1 && DFS(i - 1, j,pos + 1)) return true; if (i < m && DFS(i + 1, j,pos + 1)) return true; if (j > 1 && DFS(i, j - 1,pos + 1)) return true; if (j < n && DFS(i, j + 1,pos + 1)) return true; data[i - 1][j - 1] = c; return false; } } else return false; } private: int m, n; string _word; vector> data; };