单词搜索

发表于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

LeetCode每日一题，79. Word Search

先看题目描述

大意就是给定一个二维矩阵表示网格，问给定的单词是否存在于网格中，且单词必须按照字母顺序，通过相邻的单元格内字母构成，同一单元格内的字母不允许重复使用

算法和思路

这题和前几天的题差不多，也是使用深度优先搜索与回溯就可以，大致就是遍历每个单元格中的字母，若与单词的首字母相同，则从那个单元格开始依次访问相邻节点进行深度优先搜索，用一个矩阵 visited 记录单元格内的字母是否在路径上。例如 board[i][j] 中字母与单词首字母相同，则置 visited[i][j] 为 true，并从该单元格开始深度优先搜索，若 board[i+1][j] 与单词第二个字母相同，则置 visited[i + 1][j] 为 true，然后从 board[i + 1][j] 开始深度优先搜索，若搜索失败，则回溯，令 visited[i + 1][j] 为 false。若搜索至某单元格内字母与单词的末尾字母相同，则代表搜索成功。就这样从每个与单词首字母相同的单元格开始深度优先搜索，有一个搜索成功，则返回 true，若每个都搜索失败，则返回 false

算法源码

深度优先搜索与回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && dfs(i, j, 0, word, board, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int x, int y, int index, String word, char[][] board, boolean[][] visited) {
        if (x >= board.length || x < 0) return false;
        if (y >= board[0].length || y < 0) return false;
        if (visited[x][y]) return false;
        if (board[x][y] != word.charAt(index)) return false;
        visited[x][y] = true;
        if (index == word.length() - 1 && board[x][y] == word.charAt(index)) return true;
        if (!(dfs(x + 1, y, index + 1, word, board, visited) || dfs(x - 1, y, index + 1, word, board, visited) || dfs(x, y + 1, index + 1, word, board, visited) || dfs(x, y - 1, index + 1, word, board, visited))) {
            visited[x][y] = false;
            return false;
        }
        return true;
    }
}