给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" 输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd" 输出：false
提示：
1 <= board.length <= 2001 <= board[i].length <= 200board和word仅由大小写英文字母组成
注意：本题与主站 79 题相同：https://leetcode.cn/problems/word-search/
深度优先搜索 DFS 解决。
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, k):
if k == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or word[k] != board[i][j]:
return False
board[i][j] = ''
ans = any(
dfs(i + a, j + b, k + 1) for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]
)
board[i][j] = word[k]
return ans
m, n = len(board), len(board[0])
return any(dfs(i, j, 0) for i in range(m) for j in range(n))class Solution {
private char[][] board;
private String word;
private int m;
private int n;
public boolean exist(char[][] board, String word) {
m = board.length;
n = board[0].length;
this.board = board;
this.word = word;
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 k) {
if (k == word.length()) {
return true;
}
if (i < 0 || i >= m || j < 0 || j >= n || word.charAt(k) != board[i][j]) {
return false;
}
board[i][j] = ' ';
int[] dirs = {-1, 0, 1, 0, -1};
boolean ans = false;
for (int l = 0; l < 4; ++l) {
ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1);
}
board[i][j] = word.charAt(k);
return ans;
}
}/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board, word) {
const m = board.length;
const n = board[0].length;
let dfs = function (i, j, k) {
if (k == word.length) {
return true;
}
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k]) {
return false;
}
board[i][j] = ' ';
let ans = false;
let dirs = [-1, 0, 1, 0, -1];
for (let l = 0; l < 4; ++l) {
ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1);
}
board[i][j] = word[k];
return ans;
};
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
};func exist(board [][]byte, word string) bool {
m, n := len(board), len(board[0])
var dfs func(i, j, k int) bool
dfs = func(i, j, k int) bool {
if k == len(word) {
return true
}
if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k] {
return false
}
board[i][j] = ' '
dirs := []int{-1, 0, 1, 0, -1}
ans := false
for l := 0; l < 4; l++ {
ans = ans || dfs(i+dirs[l], j+dirs[l+1], k+1)
}
board[i][j] = word[k]
return ans
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if dfs(i, j, 0) {
return true
}
}
}
return false
}class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j)
if (dfs(i, j, 0, board, word))
return 1;
return 0;
}
bool dfs(int i, int j, int k, vector<vector<char>>& board, string word) {
if (k == word.size()) return 1;
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[k]) return 0;
vector<int> dirs = {-1, 0, 1, 0, -1};
board[i][j] = ' ';
bool ans = 0;
for (int l = 0; l < 4; ++l)
ans = ans || dfs(i + dirs[l], j + dirs[l + 1], k + 1, board, word);
board[i][j] = word[k];
return ans;
}
};function exist(board: string[][], word: string): boolean {
const m = board.length;
const n = board[0].length;
const dfs = (i: number, j: number, k: number) => {
if ((board[i] ?? [])[j] !== word[k]) {
return false;
}
if (++k === word.length) {
return true;
}
const temp = board[i][j];
board[i][j] = ' ';
if (
dfs(i + 1, j, k) ||
dfs(i, j + 1, k) ||
dfs(i - 1, j, k) ||
dfs(i, j - 1, k)
) {
return true;
}
board[i][j] = temp;
return false;
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (dfs(i, j, 0)) {
return true;
}
}
}
return false;
}impl Solution {
fn dfs(board: &mut Vec<Vec<char>>, chars: &Vec<char>, i: usize, j: usize, mut k: usize) -> bool {
if board[i][j] != chars[k] {
return false;
}
k += 1;
if k == chars.len() {
return true;
}
let temp = board[i][j];
board[i][j] = ' ';
if i != 0 && Self::dfs(board, chars, i - 1, j, k)
|| j != 0 && Self::dfs(board, chars, i, j - 1, k)
|| i != board.len() - 1 && Self::dfs(board, chars, i + 1, j, k)
|| j != board[0].len() - 1 && Self::dfs(board, chars, i, j + 1, k)
{
return true;
}
board[i][j] = temp;
false
}
pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
let m = board.len();
let n = board[0].len();
let chars = word.chars().collect::<Vec<char>>();
for i in 0..m {
for j in 0..n {
if Self::dfs(&mut board, &chars, i, j, 0) {
return true;
}
}
}
false
}
}public class Solution {
public bool Exist(char[][] board, string word) {
int k = 0;
for (int i = 0; i < board.Length; i++)
{
for (int j = 0; j < board[0].Length; j++)
{
if (dfs(board, word, i, j, k)) {
return true;
}
}
}
return false;
}
public bool dfs(char[][] board, string word, int i, int j, int k) {
if (i > board.Length - 1 || i < 0 || j > board[0].Length - 1 || j < 0 || board[i][j] != word[k]) {
return false;
}
if (k == word.Length - 1) {
return true;
}
board[i][j] = '\0';
bool res = dfs(board, word, i+1, j, k+1) || dfs(board, word, i, j+1, k+1) || dfs(board, word, i-1, j, k+1) || dfs(board, word, i, j-1, k+1);
board[i][j] = word[k];
return res;
}
}