[Lintcode]132. Word Search II /[Leetcode]212. Word Search II

2024-01-02 11:38

本文主要是介绍[Lintcode]132. Word Search II /[Leetcode]212. Word Search II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

132. Word Search II / 212. Word Search II

  • 本题难度: Hard
  • Topic: Data Structure - Tire/DFS

Description

Given a 2D board and a list of words from the dictionary, find all words in the board.

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

Example:

Input:
words = [“oath”,“pea”,“eat”,“rain”] and board =
[
[‘o’,‘a’,‘a’,‘n’],
[‘e’,‘t’,‘a’,‘e’],
[‘i’,‘h’,‘k’,‘r’],
[‘i’,‘f’,‘l’,‘v’]
]

Output: [“eat”,“oath”]

别人的代码

class Solution:#def findWords(self, board: 'List[List[str]]', words: 'List[str]') -> 'List[str]':def findWords(self, board, words):trie = {}for w in words:t = triefor c in w:if c not in t:t[c] = {}t = t[c]t['#'] = '#'res = []for i in range(len(board)):for j in range(len(board[0])):self.find(board, i, j, trie, '', res)return list(set(res))def find(self, board, i, j, trie, path, res):if '#' in trie:res.append(path)if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or board[i][j] not in trie:returntmp = board[i][j]board[i][j] ="@"self.find(board, i+1, j, trie[tmp], path+tmp, res)self.find(board, i, j+1, trie[tmp], path+tmp, res)self.find(board, i-1, j, trie[tmp], path+tmp, res)self.find(board, i, j-1, trie[tmp], path+tmp, res)board[i][j] = tmp

思路
是79. Word Search的升级版。不仅仅用了DFS还用Tire进行了优化。使得查找各个单词时不用依次从头到尾查找,而是共用了前缀。
因为之前没有写过Tire,所以我选择看一看discussion。

字典树

https://blog.csdn.net/chivalrousli/article/details/41487953

Trie的过程

构建一个字典树的方法代码

words = ["oath","pea","eat","rain","peakja","peal"]trie = {} #4339361904
for w in words:#print(trie)t = trie  #4339361904#print(id(t),id(trie))for c in w:if c not in t: #不存在相同前缀的单词已在字典树t[c] = {} #t:4339361904 #t[c]: 4339361976print(id(t),t)t = t[c] #t:4339361976print(id(t),t)print("*****")t['#'] = '#'
print(id(trie))

trie 和初始的t在4339361904:
字典t中key为c的val:{}存储在4339361976中,然后将t指向t[c]的位置,相当于t得到了更新。
tire有点像链表的表头。
【Python】变量类型、变量名、内存地址

  • 时间复杂度
    使用trie 对有相同前缀的单词有优化,但是时间复杂度没变

这篇关于[Lintcode]132. Word Search II /[Leetcode]212. Word Search II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

哈希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

AI基础 L9 Local Search II 局部搜索

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

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)模型放置目录(重要)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

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

题目: 题解: 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 & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样