题目要求:
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true
示例 2:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true
示例 3:
输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false
提示:m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/word-search
解题代码:
class Solution { private: int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; int m, n; vector<vector<bool>> visited; bool inArea(int x, int y) { return x >= 0 && x < m && y >= 0 && y <n; } // 从board[startx][starty]开始,寻找word[index...word.size()) bool searchWord(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]) { visited[startx][starty] = true; // 从startx,starty出发,向四个方向寻找 for (int i = 0; i < 4; ++i) { int newx = startx + d[i][0]; int newy = starty + d[i][1]; if (inArea(newx, newy) && !visited[newx][newy] && searchWord(board, word, index + 1, newx, newy)) return true; } visited[startx][starty] = false; } return false; } public: bool exist(vector<vector<char>>& board, string word) { m = board.size(); assert(m > 0); n = board[0].size(); visited = vector<vector<bool>>(m, vector<bool>(n, false)); for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { if (searchWord(board, word, 0, i, j)) return true; } } return false; } };