# 问题 原题链接：[https://leetcode.com/problems/word-search/](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. ``` # 分析过程 - 输入：二维字母表和需要寻找的字符串 - 输出：能否在字母表里找到 - 思路：回溯法。先找到可能的起点，然后依次从起点出发进行递归搜索并回溯。见注释。 # 解决方法 ```cpp class Solution { public: struct Point { int y; int x; }; vector<Point> find(vector<vector<char>>& board, char c) { vector<Point> result; for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board.at(0).size(); j++) { if (board[i][j] == c) { result.push_back({i, j}); } } } return result; } bool goback(vector<vector<char>>& board, const char *str, Point& p) { // 字符串找完了，返回成功 if (*(str + 1) == '\0') { return true; } // 向四个方向找 vector<Point> locations = { {p.y - 1, p.x}, {p.y + 1, p.x}, {p.y, p.x - 1}, {p.y, p.x + 1} }; for (Point location : locations) { // 判断有没有越界 if (location.y < 0 || location.y >= board.size() || location.x < 0 || location.x >= board[0].size()) { continue; } // 找到下一个字符了 if (board[location.y][location.x] == *(str + 1)) { // 标记成- board[location.y][location.x] = '-'; // 递归 if (goback(board, str + 1, location)) { return true; } // 回溯 board[location.y][location.x] = *(str + 1); } } return false; } bool exist(vector<vector<char>>& board, string word) { const char *str = word.c_str(); // 找起点 vector<Point> firstLocations = find(board, str[0]); // 只有一个字符的情况 if (word.size() == 1) { return firstLocations.size() > 0; } // 遍历所有可能的起点 for (Point location : firstLocations) { // 把当前点标记成-表示已经走过了，避免重复 board[location.y][location.x] = '-'; // 递归 if (goback(board, str, location)) { return true; } // 回溯 board[location.y][location.x] = *str; } return false; } }; ```