关注Java领域相关技术 记录有趣的事情

LeetCode-79. 单词搜索

US-B.Ralph
US-B.Ralph
2020-09-13

问题地址

LeetCode每日一题/2020-09-13

LeetCode79. 单词搜索

问题描述

规则

  • 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
  • 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例

  • 示例一：
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示

  • $board$ 和 $word$ 中只包含大写和小写英文字母。
  • $1 <= board.length <= 200$
  • $1 <= board[i].length <= 200$
  • $1 <= word.length <= 10^3$

解析

解题思路

  • 从x,y出发开始搜索字符 chars[index]，同时由与board大小相同的visited记录下x,y是否访问过；
    • 如果board[x][y]==chars[index]，则visited[x][y]记录为true，并且搜索与x,y相邻的其他位置是否等于 chars[++index]；
    • 与[y]相邻的位置为：

数据操作分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0079_WordSearch {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        if (m == 0 || word.length() == 0) return false;
        int n = board[0].length;
        char[] chars = word.toCharArray();
        boolean[][] visited = new boolean[m][n];
        int index = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, chars, index, i, j, visited)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] chars, int index, int x, int y, boolean[][] visited) {

        if (index == chars.length - 1) return board[x][y] == chars[index];

        int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        if (board[x][y] == chars[index]) {
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int nextX = x + dir[i][0];
                int nextY = y + dir[i][1];
                if (inArea(nextX, nextY, board) && !visited[nextX][nextY]) {
                    if (dfs(board, chars, index + 1, nextX, nextY, visited)) return true;
                }

            }
            visited[x][y] = false;
        }

        return false;
    }

    private boolean inArea(int nextX, int nextY, char[][] board) {
        if (nextX < 0 || nextY < 0 || nextX >= board.length || nextY >= board[0].length) return false;
        return true;
    }
}

官方解法

方法一：深度优先搜索

思路：

  • 设函数 \text{check}(i, j, k) 判断以网格的 (i, j) 位置出发，能否搜索到单词 \text{word}[k..]，其中 \text{word}[k..] 表示字符串 \text{word} 从第 k 个字符开始的后缀子串。如果能搜索到，则返回 \text{true}，反之返回 \text{false}。函数 \text{check}(i, j, k) 的执行步骤如下：
    • 如果 \text{board}[i][j] \neq s[k]，当前字符不匹配，直接返回 \text{false}。
    • 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回 \text{true}true。
    • 否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 \text{word}[k+1..]，则返回 \text{true}，否则返回 \text{false}。
  • 这样，我们对每一个位置 (i,j) 都调用函数 \text{check}(i, j, 0) 进行检查：只要有一处返回 \text{true}，就说明网格中能够找到相应的单词，否则说明不能找到。
  • 为了防止重复遍历相同的位置，需要额外维护一个与 \text{board} 等大的 \text{visited} 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。

复杂度分析

  1. 时间复杂度 一个非常宽松的上界为 O(MN \cdot 3^L)，其中 M, N 为网格的长度与宽度，L 为字符串 \text{word} 的长度。在每次调用函数 \text{check} 时，除了第一次可以进入 4 个分支以外，其余时间我们最多会进入 3 个分支（因为每个位置只能使用一次，所以走过来的分支没法走回去）。由于单词长为 L，故 \text{check(i, j, 0)} 的时间复杂度为 O(3^L)，而我们要执行 O(MN) 次检查。然而，由于剪枝的存在，我们在遇到不匹配或已访问的字符时会提前退出，终止递归流程。因此，实际的时间复杂度会远远小于 \Theta(MN \cdot 3^L)。

  2. 空间复杂度：O(MN)。我们额外开辟了 O(MN) 的 \text{visited} 数组，同时栈的深度最大为 O(\min(L, MN))。

编码实现

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}

精彩评论

跳转地址1：在二维平面上使用回溯法（Python 代码、Java 代码）

思路

编码实现

public class Solution {

    private boolean[][] marked;

    //        x-1,y
    // x,y-1  x,y    x,y+1
    //        x+1,y
    private int[][] direction = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
    // 盘面上有多少行
    private int m;
    // 盘面上有多少列
    private int n;
    private String word;
    private char[][] board;

    public boolean exist(char[][] board, String word) {
        m = board.length;
        if (m == 0) {
            return false;
        }
        n = board[0].length;
        marked = new boolean[m][n];
        this.word = word;
        this.board = board;

        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 start) {
        if (start == word.length() - 1) {
            return board[i][j] == word.charAt(start);
        }
        if (board[i][j] == word.charAt(start)) {
            marked[i][j] = true;
            for (int k = 0; k < 4; k++) {
                int newX = i + direction[k][0];
                int newY = j + direction[k][1];
                if (inArea(newX, newY) && !marked[newX][newY]) {
                    if (dfs(newX, newY, start + 1)) {
                        return true;
                    }
                }
            }
            marked[i][j] = false;
        }
        return false;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    public static void main(String[] args) {

//        char[][] board =
//                {
//                        {'A', 'B', 'C', 'E'},
//                        {'S', 'F', 'C', 'S'},
//                        {'A', 'D', 'E', 'E'}
//                };
//
//        String word = "ABCCED";


        char[][] board = {{'a', 'b'}};
        String word = "ba";
        Solution solution = new Solution();
        boolean exist = solution.exist(board, word);
        System.out.println(exist);
    }
}

跳转地址2：深度优先搜索与回溯详解

思路

  • 使用深度优先搜索（DFS）和回溯的思想实现。关于判断元素是否使用过，我用了一个二维数组 mark 对使用过的元素做标记。

外层：遍历

  • 首先遍历 board 的所有元素，先找到和 word 第一个字母相同的元素，然后进入递归流程。假设这个元素的坐标为 (i, j)，进入递归流程前，先记得把该元素打上使用过的标记：
mark[i][j] = 1

内层：递归

  • 好了，打完标记了，现在我们进入了递归流程。递归流程主要做了这么几件事：
    • 从 (i, j) 出发，朝它的上下左右试探，看看它周边的这四个元素是否能匹配 word 的下一个字母
      • 如果匹配到了：带着该元素继续进入下一个递归
      • 如果都匹配不到：返回 False
    • 当 word 的所有字母都完成匹配后，整个流程返回 True

几个注意点

  • 递归时元素的坐标是否超过边界
  • 回溯标记 mark[i][j] = 0以及 return 的时机

编码实现

class Solution(object):

    # 定义上下左右四个行走方向
    directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        m = len(board)
        if m == 0:
            return False
        n = len(board[0])
        mark = [[0 for _ in range(n)] for _ in range(m)]

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0]:
                    # 将该元素标记为已使用
                    mark[i][j] = 1
                    if self.backtrack(i, j, mark, board, word[1:]) == True:
                        return True
                    else:
                        # 回溯
                        mark[i][j] = 0
        return False


    def backtrack(self, i, j, mark, board, word):
        if len(word) == 0:
            return True

        for direct in self.directs:
            cur_i = i + direct[0]
            cur_j = j + direct[1]

            if cur_i >= 0 and cur_i < len(board) and cur_j >= 0 and cur_j < len(board[0]) and board[cur_i][cur_j] == word[0]:
                # 如果是已经使用过的元素，忽略
                if mark[cur_i][cur_j] == 1:
                    continue
                # 将该元素标记为已使用
                mark[cur_i][cur_j] = 1
                if self.backtrack(cur_i, cur_j, mark, board, word[1:]) == True:
                    return True
                else:
                    # 回溯
                    mark[cur_i][cur_j] = 0
        return False
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

3 × 5 =