題目

https://leetcode.com/problems/word-search/

題解

回溯 + DFS，回溯是有后效性的，所以不能轉(zhuǎn)化為 DP

class Solution {int M;int N;public boolean exist(char[][] board, String word) {M = board.length;N = board[0].length;for (int i = 0; i < M; i++) {for (int j = 0; j < N; j++) {if (dfs(word, 0, i, j, board, new boolean[M][N])) return true;}}return false;}public boolean dfs(String word, int index, int i, int j, char[][] board, boolean[][] visited) {if (index == word.length()) return true;if (i < 0 || i == M || j < 0 || j == N || visited[i][j] || board[i][j] != word.charAt(index)) return false;visited[i][j] = true;boolean result = dfs(word, index + 1, i + 1, j, board, visited) ||dfs(word, index + 1, i - 1, j, board, visited) ||dfs(word, index + 1, i, j + 1, board, visited) ||dfs(word, index + 1, i, j - 1, board, visited);visited[i][j] = false;return result;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 79. Word Search | 79. 单词搜索（回溯+DFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。