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

本文主要是介绍[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

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

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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---