Medium!
题目描述:
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =[ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E']]给定 word = "ABCCED", 返回 true.给定 word = "SEE", 返回 true.给定 word = "ABCB", 返回 false.
解题思路:
这道题是典型的深度优先遍历DFS的应用,原二维数组就像是一个迷宫,可以上下左右四个方向行走,我们以二维数组中每一个数都作为起点和给定字符串做匹配,我们还需要一个和原数组等大小的visited数组,是bool型的,用来记录当前位置是否已经被访问过,因为题目要求一个cell只能被访问一次。如果二维数组board的当前字符和目标字符串word对应的字符相等,则对其上下左右四个邻字符分别调用DFS的递归函数,只要有一个返回true,那么就表示可以找到对应的字符串,否则就不能找到。
C++解法一:
1 class Solution { 2 public: 3 bool exist(vector>& board, string word) { 4 if (board.empty() || board[0].empty()) return false; 5 int m = board.size(), n = board[0].size(); 6 vector > visited(m, vector (n, false)); 7 for (int i = 0; i < m; ++i) { 8 for (int j = 0; j < n; ++j) { 9 if (search(board, word, 0, i, j, visited)) return true;10 }11 }12 return false;13 }14 bool search(vector >& board, string word, int idx, int i, int j, vector >& visited) {15 if (idx == word.size()) return true;16 int m = board.size(), n = board[0].size();17 if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[idx]) return false;18 visited[i][j] = true;19 bool res = search(board, word, idx + 1, i - 1, j, visited) 20 || search(board, word, idx + 1, i + 1, j, visited)21 || search(board, word, idx + 1, i, j - 1, visited)22 || search(board, word, idx + 1, i, j + 1, visited);23 visited[i][j] = false;24 return res;25 }26 };
我们还可以不用visited数组,直接对board数组进行修改,将其遍历过的位置改为井号,记得递归调用完后需要恢复之前的状态。
C++解法二:
1 class Solution { 2 public: 3 bool exist(vector>& board, string word) { 4 if (board.empty() || board[0].empty()) return false; 5 int m = board.size(), n = board[0].size(); 6 for (int i = 0; i < m; ++i) { 7 for (int j = 0; j < n; ++j) { 8 if (search(board, word, 0, i, j)) return true; 9 }10 }11 return false;12 }13 bool search(vector >& board, string word, int idx, int i, int j) {14 if (idx == word.size()) return true;15 int m = board.size(), n = board[i].size();16 if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[idx]) return false;17 char c = board[i][j];18 board[i][j] = '#';19 bool res = search(board, word, idx + 1, i - 1, j) 20 || search(board, word, idx + 1, i + 1, j)21 || search(board, word, idx + 1, i, j - 1)22 || search(board, word, idx + 1, i, j + 1);23 board[i][j] = c;24 return res;25 }26 };