給定一個二維網格和一個單詞，找出該單詞是否存在于網格中。

單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。

示例:

board =
[
? ['A','B','C','E'],
? ['S','F','C','S'],
? ['A','D','E','E']
]

給定 word = "ABCCED", 返回 true.
給定 word = "SEE", 返回 true.
給定 word = "ABCB", 返回 false.

思路：搜索回溯基本上是經典模板題了。

class Solution {private boolean[][] marked;// x-1,y// x,y-1 x,y x,y+1// x+1,yprivate int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};// 盤面上有多少行private int m;// 盤面上有多少列private int n;private String word;private char[][] board;public boolean exist(char[][] board, String word) {m = board.length;if (m == 0)return false;n = board[0].length;marked = new boolean[m][n];this.word = word;this.board = board;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (dfs(i, j, 0))return true;return false;}private boolean dfs(int i, int j, int start) {if (start == word.length() - 1) {return board[i][j] == word.charAt(start);}if (board[i][j] == word.charAt(start)) {marked[i][j] = true;for (int k = 0; k < 4; k++) {int newX = i + direction[k][0];int newY = j + direction[k][1];if (newX >= 0 && newX < m && newY >= 0 && newY < n && !marked[newX][newY]) {if (dfs(newX, newY, start + 1)) {return true;}}}marked[i][j] = false;}return false;} }

?

總結

以上是生活随笔為你收集整理的leetcode79. 单词搜索 网格地图搜索+回溯经典写法啦的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。