LeetCode 212.单词搜索II

2024-05-11 10:20
文章标签 leetcode 搜索 单词 ii 212

本文主要是介绍LeetCode 212.单词搜索II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

https://leetcode.cn/problems/word-search-ii/description/?envType=study-plan-v2&envId=top-interview-150

文章目录

  • 题目描述
  • 解题思路
  • 代码实现

题目描述

给定一个 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”]
输出:[]

提示:

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 中的所有字符串互不相同

解题思路

我们使用字典树把words中的所有单词存起来,同时为了便于查找子节点,我们的字典树实现的时候,可以把子节点的实现方式换位HashMap<Integer, String>这样可以实现快速查找,而且可以按需建立子节点

然后对我们的board进行dfs遍历,查找当前遍历的字符串是否在字典树中

  • 剪枝:每当当前访问的节点不是字典树中的任意一个单词的前缀,剪掉
  • 去重:同一个单词可能在多个不同的路径出现,所以使用哈希集合对结果去重。
  • dfs遍历当前节点之前,可以修改当前节点为’#', 遍历完在恢复
  • 优化:删除匹配的单词,考虑以下情况。假设给定一个所有单元格都是 a 的二维字符网格和单词列表 [“a”, “aa”, “aaa”, “aaaa”] 。当我们使用方法一来找出所有同时在二维网格和单词列表中出现的单词时,我们需要遍历每一个单元格的所有路径,会找到大量重复的单词。

代码实现

class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};public List<String> findWords(char[][] board, String[] words) {Trie trie = new Trie();for(String word: words) {   // 插入字典树trie.insert(word);}Set<String> ans = new HashSet<String>();  // 结果集去重for(int i=0; i<board.length; i++){for(int j=0; j<board[0].length; j++){dfs(board, trie,i,j,ans);      // dfs}}return new ArrayList<String>(ans);}public void dfs(char[][] board, Trie now , int i1, int j1, Set<String> ans){if(!now.children.containsKey(board[i1][j1])){   // 剪枝return;}char ch = board[i1][j1];now = now.children.get(ch);if(!"".equals(now.word)){ans.add(now.word);now.word = "";     // 优化,这样省的去重}board[i1][j1] = '#';for(int[] dir: dirs){int i2 = i1 + dir[0];int j2 = j1 + dir[1];if(i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length){dfs(board, now, i2, j2, ans);}}board[i1][j1] = ch;}
}class Trie{String word;Map<Character, Trie> children;    // 子节点实现方式换位hashMap// boolean isWord; // 这里暂时没用public Trie(){this.word = "";this.children = new HashMap<Character, Trie>();}public void insert(String word){Trie cur = this;for(int i=0; i< word.length(); i++){char c = word.charAt(i);if(!cur.children.containsKey(c)){cur.children.put(c, new Trie());}cur = cur.children.get(c);}cur.word = word;}
}

这篇关于LeetCode 212.单词搜索II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/979263

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)