题目描述

单词搜索（Word Search）

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

示例 1:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"

输出: true

示例 2:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "SEE"

输出: true

示例 3:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCB"

输出: false

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;
}

// 使用示例
$board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
];
$word = "ABCCED";
var_dump(exist($board, $word)); // 输出: bool(true)

Python 示例代码

def exist(board, word):
    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

# 使用示例
board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
]
word = "ABCCED"
print(exist(board, word))  # 输出: True

JavaScript 示例代码

function exist(board, word) {
    const rows = board.length;
    const cols = board[0].length;
    
    const dfs = (row, col, index) => {
        if (index === word.length) return true;
        if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] !== word[index]) {
            return false;
        }
        const temp = board[row][col];
        board[row][col] = '#';  // 标记为已访问
        
        const found = dfs(row - 1, col, index + 1) ||  // 上
                      dfs(row + 1, col, index + 1) ||  // 下
                      dfs(row, col - 1, index + 1) ||  // 左
                      dfs(row, col + 1, index + 1);    // 右
        
        board[row][col] = 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;
}

// 使用示例
const board = [
    ['A','B','C','E'],
    ['S','F','C','S'],
    ['A','D','E','E']
];
const word = "ABCCED";
console.log(exist(board, word));  // 输出: true

这些示例展示了如何使用深度优先搜索（DFS）算法来解决单词搜索问题。每个示例都包含了一个辅助的DFS函数，用于递归地探索网格，并判断是否存在从当前位置开始的路径，能够按顺序匹配给定的单词。