力扣第 212 题
题目
给定一个 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.lengthn == board[i].length1 <= m, n <= 12board[i][j] 是一个小写英文字母1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i] 由小写英文字母组成words 中的所有字符串互不相同
分析
- 0079 的升级版，变成搜索多个单词
- 单词数量太多，一个个搜会超时，考虑怎么同时搜索：
- 只要搜索路径是某一个单词的前缀，就可以继续搜索
- 否则，可以直接跳出
- 当搜索路径匹配某一个单词时，添加到结果中即可
- 于是想到用 trie 树，方便判断路径是否单词前缀或单词本身
- 注意不同路径可能找到相同单词，结果要去重
解答
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m,n = len(board),len(board[0])
T = lambda:defaultdict(T)
trie = T()
for w in words:
p = trie
for c in w:
p = p[c]
p['#'] = w
def dfs(p,i,j):
if '#' in p:
res.add(p['#'])
A = product(range(m),range(n)) if p==trie else [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]
for x,y in A:
if 0<=x<m and 0<=y<n and board[x][y] in p:
c = board[x][y]
board[x][y] = ''
dfs(p[c],x,y)
board[x][y] = c
res = set()
dfs(trie,-1,-1)
return list(res)
|
4710 ms
*附加
针对本题有巧妙的优化：
- 找到单词的同时将 ‘#’ 弹出，就不会搜索到相同单词，最后无需再去重
- 弹出 ‘#’ 后，非 ‘#’ 的叶子结点也可以弹出，无需再考虑
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m,n = len(board),len(board[0])
T = lambda:defaultdict(T)
trie = T()
for w in words:
p = trie
for c in w:
p = p[c]
p['#'] = w
def dfs(p,i,j):
if '#' in p:
res.append(p.pop('#'))
A = product(range(m),range(n)) if p==trie else [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]
for x,y in A:
if 0<=x<m and 0<=y<n and board[x][y] in p:
c = board[x][y]
board[x][y] = ''
dfs(p[c],x,y)
board[x][y] = c
if not p[c]:
p.pop(c)
res = []
dfs(trie,-1,-1)
return res
|
506 ms