mzoe666888

V1

2022/04/19阅读:33主题:兰青

内卷大厂系列《单词搜索二连击》

大厂高频算法面试题:《单词搜索系列》,您将学到如何利用深度优先遍历解决单词搜索问题,以及回溯过程清理现场(清理痕迹)技巧,其次如何利用前缀树加速单词查找的过程。

一、单词搜索 I

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

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

示例 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

leetcode

1、分析

进阶:你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?

我们需要考虑怎么不走回头路?怎么建立不走回头路的机制?

利用深度优先遍历,每走过的路都标记上,当这条路走不通的时候(从上一直走到头,从下一直走到头,从左一直走到头,从右一直走到头),往回返的时候要记得清理现场(恢复现场痕迹),这是深度优先遍历经常需要考虑的点,防止走重复路。

时间复杂度怎么算? 看似递归很暴力,其实就是最优解,矩阵中的每个点(路)都试一遍,每个点过一遍,加上4个方向判断,即每个点过5遍,忽略常数项,所以时间复杂度为O(N*M)

2、实现

public static boolean exist(char[][] board, String word) {
    char[] w = word.toCharArray();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (process(board, i, j, w, 0)) {
                return true;
            }
        }
    }
    return false;
}

// 目前到达了b[i][j],word[k....]
// 从b[i][j]出发,能不能搞定word[k....]  true  false
public static boolean process(char[][] b, int i, int j, char[] w, int k) {
    if (k == w.length) { // base case
        return true;
    }
    // 边界判断
    if (i < 0 || i == b.length || j < 0 || j == b[0].length) {
        return false;
    }
    if (b[i][j] != w[k]) { // 当前路字符都搞不定当前字符,直接返回false
        return false;
    }
    // k 有字符
    char tmp = b[i][j];
    b[i][j] = 0// 标记现场
    // 后续上下左右4个方向只要1个方向走通即可
    boolean ans = process(b, i - 1, j, w, k + 1// 往上走
        || process(b, i + 1, j, w, k + 1// 往下走
        || process(b, i, j - 1, w, k + 1// 往左走
        || process(b, i, j + 1, w, k + 1); // 往右走
    b[i][j] = tmp; // 恢复现场
    return ans;
}

二、单词搜索 II

给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words, 返回所有二维网格上的单词 。

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

示例 1

输入:board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出:["eat","oath"]

示例 2

输入:board = [["a","b"],["c","d"]], words = ["abcb"]
输出:[]

leetcode

1、分析

一个单词内部走过的路不能重复走

  • 走的过程中,怎么知道单词走出来了,需要一种机制

  • 最好设计成深度优先遍历,走过的路打上标签,比如从左一直走到头,然后回到最初位置,再从右一直走到头,再回到最初位置,再从上一直走到头,再回到最初位置,再从下一直走到头。

利用前缀树,把words所有的单词都加入到前缀树中

在走的过程中,利用前缀树知道哪些方向不用走,起到加速作用

递归函数返回int类型,代表从当前字符位置出发,后续收集了多少个单词(fix表示)

如果cur.pass - fix = 0,说明之前已经收集过这些单词了,不用重复的走,起到加速的过程。

不懂什么是前缀树,可参考这篇文章《前缀树-TrieTree-学习之旅》

2、实现

// 前缀树结构
public static class TrieNode {
    public TrieNode[] nexts;
    public int pass;
    public int end;

    public TrieNode() {
        nexts = new TrieNode[26];
        pass = 0;
        end = 0;
    }

}

// 往前缀树上添加单词
public static void fillWord(TrieNode head, String word) {
    head.pass++;
    char[] chs = word.toCharArray();
    int index = 0;
    TrieNode node = head;
    for (int i = 0; i < chs.length; i++) {
        index = chs[i] - 'a';
        if (node.nexts[index] == null) {
            node.nexts[index] = new TrieNode();
        }
        node = node.nexts[index];
        node.pass++;
    }
    node.end++;
}

public static String generatePath(LinkedList<Character> path) {
    char[] str = new char[path.size()];
    int index = 0;
    for (Character cha : path) {
        str[index++] = cha;
    }
    return String.valueOf(str);
}

public static List<String> findWords(char[][] board, String[] words) {
    TrieNode head = new TrieNode(); // 前缀树最顶端的头
    HashSet<String> set = new HashSet<>(); // 防止添加重复单词
    for (String word : words) {
        if (!set.contains(word)) {
            fillWord(head, word);
            set.add(word);
        }
    }
    // 答案
    List<String> ans = new ArrayList<>();
    // 沿途走过的字符,收集起来,存在path里
    LinkedList<Character> path = new LinkedList<>();
    for (int row = 0; row < board.length; row++) {
        for (int col = 0; col < board[0].length; col++) {
            // 枚举在board中的所有位置
            // 每一个位置出发的情况下,答案都收集
            process(board, row, col, path, head, ans);
        }
    }
    return ans;
}

// 从board[row][col]位置的字符出发,
// 之前的路径上,走过的字符,记录在path里
// cur还没有登上,有待检查能不能登上去的前缀树的节点
// 如果找到words中的某个str,就记录在 res里
// 返回值,从row,col 出发,一共找到了多少个str
public static int process(
    char[][] board,
    int row, int col,
    LinkedList<Character> path,
    TrieNode cur,
    List<String> res)
 
{
    char cha = board[row][col];
    if (cha == 0) { // 这个row col位置是之前走过的位置,是回头路
        return 0;
    }
    // (row,col) 不是回头路   cha 有效
    int index = cha - 'a';
    // 如果没路,或者这条路上最终的字符串之前加入过结果里
    if (cur.nexts[index] == null || cur.nexts[index].pass == 0) {
        return 0;
    }
    // 没有走回头路且能登上去
    cur = cur.nexts[index];
    path.addLast(cha);// 当前位置的字符加到路径里去
    int fix = 0// 从row和col位置出发,后续一共搞定了多少答案
    // 当我来到row col位置,如果决定不往后走了。是不是已经搞定了某个字符串了
    if (cur.end > 0) {
        res.add(generatePath(path));
        cur.end--;
        fix++;
    }
    // 往上、下、左、右,四个方向尝试
    board[row][col] = 0// 标记走过了,将自己的ASCII标记为0
    if (row > 0) { // 往上走
        fix += process(board, row - 1, col, path, cur, res);
    }
    if (row < board.length - 1) { // 往下走
        fix += process(board, row + 1, col, path, cur, res);
    }
    if (col > 0) { // 往左走
        fix += process(board, row, col - 1, path, cur, res);
    }
    if (col < board[0].length - 1) { // 往右走
        fix += process(board, row, col + 1, path, cur, res);
    }
    board[row][col] = cha; // 走完再重新设置回去
    path.pollLast(); // 深度优先遍历,清理现场
    cur.pass -= fix; // fix:当前字符出发,一共走出了多少个合法的单词路径
    return fix;
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1