题目描述

单词搜索：给定一个二维网格（board）和一个单词（word），找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的格子里的字母构成，其中“相邻”格子是指水平或垂直方向上相邻的格子。同一个格子里的字母在一个单词中不允许被重复使用。

示例

输入：

• 二维网格 board:

  [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
  ]
  

• 单词 word: "ABCCED"

输出:

• true，因为单词 "ABCCED" 可以通过路径 "A" -> "B" -> "C" -> "C" -> "E" -> "D" 在网格中被找到。

PHP 示例代码

function exist($board, $word) {
    $rows = count($board);
    $cols = count($board[0]);
    
    for ($i = 0; $i < $rows; $i++) {
        for ($j = 0; $j < $cols; $j++) {
            if (dfs($board, $word, 0, $i, $j)) {
                return true;
            }
        }
    }
    
    return false;
}

function dfs(&$board, $word, $index, $row, $col) {
    $rows = count($board);
    $cols = count($board[0]);
    
    if ($index == strlen($word)) {
        return true;
    }
    
    if ($row < 0 || $row >= $rows || $col < 0 || $col >= $cols || $board[$row][$col] != $word[$index]) {
        return false;
    }
    
    $temp = $board[$row][$col];
    $board[$row][$col] = '#'; // 标记当前格子已访问
    
    $directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // 上下左右四个方向
    foreach ($directions as $dir) {
        $newRow = $row + $dir[0];
        $newCol = $col + $dir[1];
        if (dfs($board, $word, $index + 1, $newRow, $newCol)) {
            return true;
        }
    }
    
    $board[$row][$col] = $temp; // 恢复格子状态
    return false;
}

Python 示例代码

def exist(board, word):
    if not board or not board[0] or not word:
        return False
    
    rows, cols = len(board), len(board[0])
    
    def dfs(i, j, index):
        if index == len(word):
            return True
        if i < 0 or i >= rows or j < 0 or j >= cols or board[i][j] != word[index]:
            return False
        temp = board[i][j]
        board[i][j] = '#'  # 标记已访问
        found = dfs(i - 1, j, index + 1) or \
                dfs(i + 1, j, index + 1) or \
                dfs(i, j - 1, index + 1) or \
                dfs(i, j + 1, index + 1)
        board[i][j] = temp  # 恢复格子状态
        return found
    
    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return True
    return False

JavaScript 示例代码

function exist(board, word) {
    if (!board || !board[0] || !word) return false;
    
    const rows = board.length;
    const cols = board[0].length;
    
    const dfs = (i, j, index) => {
        if (index === word.length) return true;
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] !== word[index]) return false;
        const temp = board[i][j];
        board[i][j] = '#'; // 标记已访问
        const found = dfs(i - 1, j, index + 1) ||
                      dfs(i + 1, j, index + 1) ||
                      dfs(i, j - 1, index + 1) ||
                      dfs(i, j + 1, index + 1);
        board[i][j] = temp; // 恢复格子状态
        return found;
    };
    
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (dfs(i, j, 0)) return true;
        }
    }
    
    return false;
}

码小课提示

在码小课网站上，你可以找到更多关于算法和数据结构的详细讲解和练习，包括回溯算法、深度优先搜索（DFS）、广度优先搜索（BFS）等高级主题，帮助你更深入地理解和应用这些算法解决实际问题。