单词搜索

题解思路

算法思想

1. 遍历起点
   从二维网格中的每个单元格出发，作为搜索单词的起点。

2. 递归搜索
   使用 DFS 从当前单元格开始搜索，判断该位置是否与单词对应字符匹配。如果匹配，则继续向上、下、左、右四个方向搜索下一个字符。

   • 搜索时需要保证：
     • 当前坐标在网格范围内；
     • 当前单元格字符与单词当前位置字符一致；
     • 同一单元格在一个搜索路径中只使用一次（因此需要标记已访问的单元格）。

3. 回溯处理
   在搜索过程中，若某一路径无法匹配完整单词，则回溯并恢复现场，尝试其它路径。

4. 终止条件
   当搜索的索引等于单词长度时，说明整个单词已经成功匹配，返回 true；若所有起点均未匹配成功，则返回 false。

复杂度分析

• 时间复杂度：
  在最坏情况下，从每个起点都可能进行 4^(L) 次递归，其中 L 为单词长度，总体时间复杂度为 O(m * n * 4^L)。由于题目中 m、n 和 L 的取值较小，该算法能够在可接受的时间内完成搜索。

• 空间复杂度：
  递归调用栈的深度最多为 L，再加上用于标记访问的额外空间，空间复杂度为 O(L)。

Python代码

def exist(board, word):
    # 获取网格行数和列数
    m, n = len(board), len(board[0])
    
    def dfs(i, j, index):
        # 当索引达到单词长度时，匹配成功
        if index == len(word):
            return True
        # 检查边界条件和当前单元格字符是否匹配
        if i < 0 or i >= m or j < 0 or j >= n 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(m):
        for j in range(n):
            if dfs(i, j, 0):
                return True
    return False

if __name__ == "__main__":
    import sys
    input_data = sys.stdin.read().strip().split()
    if not input_data:
        exit(0)
    # 第一个和第二个数字分别为网格的行数和列数
    m = int(input_data[0])
    n = int(input_data[1])
    board = []
    index = 2
    # 读取二维网格数据
    for _ in range(m):
        row = []
        for _ in range(n):
            row.append(input_data[index])
            index += 1
        board.append(row)
    # 读取单词
    word = input_data[index]
    # 输出结果，true 表示存在，false 表示不存在
    print("true" if exist(board, word) else "false")

JAVA代码

import java.util.Scanner;

public class Main {
    // 主函数，从标准输入中读取数据（ACM模式）
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读取网格的行数 m 和列数 n
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine(); // 消耗换行符
        
        // 构造二维字符数组 board
        char[][] board = new char[m][n];
        for (int i = 0; i < m; i++) {
            String line = sc.nextLine();
            String[] tokens = line.split("\\s+");
            for (int j = 0; j < n; j++) {
                board[i][j] = tokens[j].charAt(0);
            }
        }
        // 读取要搜索的单词
        String word = sc.nextLine();
        // 输出结果：true 表示存在，false 表示不存在
        System.out.println(exist(board, word) ? "true" : "false");
        sc.close();
    }
    
    // 判断单词是否存在于网格中的函数
    public static boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        // 遍历每个单元格作为起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // 深度优先搜索（DFS）函数
    private static boolean dfs(char[][] board, String word, int i, int j, int index) {
        // 当索引达到单词长度时，匹配成功
        if (index == word.length()) {
            return true;
        }
        // 检查边界条件以及当前单元格字符是否匹配
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
            return false;
        }
        // 暂存当前字符，并标记为已访问
        char temp = board[i][j];
        board[i][j] = '#';
        // 递归搜索四个方向：下、上、右、左
        boolean found = dfs(board, word, i + 1, j, index + 1)
                     || dfs(board, word, i - 1, j, index + 1)
                     || dfs(board, word, i, j + 1, index + 1)
                     || dfs(board, word, i, j - 1, index + 1);
        // 恢复当前单元格字符
        board[i][j] = temp;
        return found;
    }
}

C++代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 深度优先搜索（DFS）函数，判断从 (i, j) 出发能否匹配单词中从 index 开始的字符
bool dfs(vector<vector<char>>& board, const string& word, int i, int j, int index) {
    // 如果 index 等于单词长度，说明全部匹配成功
    if (index == word.size()) return true;
    // 检查边界条件以及当前单元格字符是否匹配
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index])
        return false;
    // 暂存当前字符，并标记为已访问
    char temp = board[i][j];
    board[i][j] = '#';
    // 递归搜索四个方向：下、上、右、左
    bool found = dfs(board, word, i + 1, j, index + 1)
              || dfs(board, word, i - 1, j, index + 1)
              || dfs(board, word, i, j + 1, index + 1)
              || dfs(board, word, i, j - 1, index + 1);
    // 恢复当前单元格字符
    board[i][j] = temp;
    return found;
}

int main() {
    int m, n;
    // 读取网格的行数和列数
    cin >> m >> n;
    vector<vector<char>> board(m, vector<char>(n));
    // 读取二维字符网格数据
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    // 读取要搜索的单词
    string word;
    cin >> word;
    
    // 遍历每个单元格作为起点
    bool exists = false;
    for (int i = 0; i < m && !exists; i++) {
        for (int j = 0; j < n && !exists; j++) {
            if (dfs(board, word, i, j, 0)) {
                exists = true;
            }
        }
    }
    // 输出结果：true 表示存在，false 表示不存在
    cout << (exists ? "true" : "false") << endl;
    return 0;
}

Leetcode 60.单词搜索-原题链接

题目内容

给定一个 $m × n$ 二维字符网格 $board$ 和一个字符串单词 $word$ 。如果 $word$ 存在于网格中，返回 $true$ ；否则，返回 $false$ 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用

输入格式

• 第一行包含两个正整数 (m) 和 (n)，分别表示网格的行数和列数。
• 接下来 (m) 行，每行包含 (n) 个字符，中间以空格分隔，表示二维字符网格 board。
• 最后一行包含一个字符串 word。

输出格式

• 如果单词 word 在网格中存在，则输出 true；否则，输出 false。

样例输入1

3 4
A B C E
S F C S
A D E E
ABCCED

样例输出1

true

样例输入2

3 4
A B C E
S F C S
A D E E
SEE

样例输出2

true

样例输入3

3 4
A B C E
S F C S
A D E E
ABCB

样例输出3

false

提示：

• $m == board.length$
• $n = board[i].length$
• $1 <= m, n <= 6$
• $1 <= word.length <= 15$
• $board$和 $word$ 仅由大小写英文字母组成