​LeetCode刷题实战212:单词搜索 II

简介: 算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !


今天和大家聊的问题叫做
单词搜索 II,我们先来看题面:https://leetcode-cn.com/problems/word-search-ii/

Given an m x n board of characters and a list of strings words, return all words on the board.


Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

题意


给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words,找出所有同时在二维网格和字典中出现的单词。

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

示例

30.jpg

输入:board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出:["eat","oath"]
提示:
m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

解题

方法:前缀树+深度优先搜索。

public class Solution {
    private TrieNode root = new TrieNode();
    private int[] ro = {-1, 1, 0, 0};
    private int[] co = {0, 0, -1, 1};
    private void find(char[][] board, boolean[][] visited, int row, int col, TrieNode node, Set<String> founded) {
        visited[row][col] = true;
        TrieNode current = node.nexts[board[row][col]-'a'];
        if (current.word != null) founded.add(current.word);
        for(int i=0; i<4; i++) {
            int nr = row + ro[i];
            int nc = col + co[i];
            if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[nr].length || visited[nr][nc]) continue;
            TrieNode next = current.nexts[board[nr][nc]-'a'];
            if (next != null) find(board, visited, nr, nc, current, founded);
        }
        visited[row][col] = false;
    }
    public List<String> findWords(char[][] board, String[] words) {
        Set<String> founded = new HashSet<>();
        for(int i=0; i<words.length; i++) {
            char[] wa = words[i].toCharArray();
            TrieNode node = root;
            for(int j=0; j<wa.length; j++) node = node.append(wa[j]);
            node.word = words[i];
        }
        boolean[][] visited = new boolean[board.length][board[0].length];
        for(int i=0; i<board.length; i++) {
            for(int j=0; j<board[i].length; j++) {
                if (root.nexts[board[i][j]-'a'] != null) find(board, visited, i, j, root, founded);
            }
        }
        List<String> results = new ArrayList<>();
        results.addAll(founded);
        return results;
    }
}
class TrieNode {
    String word;
    TrieNode[] nexts = new TrieNode[26];
    TrieNode append(char ch) {
        if (nexts[ch-'a'] != null) return nexts[ch-'a'];
        nexts[ch-'a'] = new TrieNode();
        return nexts[ch-'a'];
    }
}

好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
19天前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
13 2
|
19天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
12 0
Leetcode第三十三题(搜索旋转排序数组)
|
18天前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
12 0
|
19天前
Leetcode(最后一个单词长度)
这篇文章介绍了两种解决LeetCode第58题的方法,即计算给定字符串中最后一个单词的长度,方法包括翻转字符串和逆向遍历统计。
15 0
|
19天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
15 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
51 6