[LeetCode]212. 单词搜索 II(Word Search II)

题目描述

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

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

示例:

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

说明:
你可以假设所有输入都由小写字母 a-z 组成。

解题思路

  • 笨办法。直接使用回溯法。
  • 使用前缀树的方法。将单词列表加入前缀树,对矩阵进行遍历。需要遍历的次数大大减少了。

代码

Python 3.6

笨办法

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
26
27
28
29
30
31
32
33
class Solution:
def findWords(self, board, words):
if len(words) == 0 or len(board) == 0 or len(board[0]) == 0:
return []
res = []
for word in words:
for i in range(len(board)):
for j in range(len(board[0])):
if word[0] == board[i][j]:
visited = []
for _ in range(len(board)):
visited.append([False] * len(board[0]))
if self.find_res(word, board, i, j, visited):
res.append(word)
break
else:
continue
break
return res

def find_res(self, string, board, i, j, visited):
if string[0] != board[i][j]:
return False
visited[i][j] = True
if len(string) == 1:
return True
if (i > 0 and board[i - 1][j] == string[1] and not visited[i - 1][j] and self.find_res(string[1:], board, i - 1, j, visited)) \
or (i < len(board) - 1 and board[i + 1][j] == string[1] and not visited[i + 1][j] and self.find_res(string[1:], board, i + 1, j, visited)) \
or (j > 0 and board[i][j - 1] == string[1] and not visited[i][j - 1] and self.find_res(string[1:], board, i, j - 1, visited)) \
or (j < len(board[0]) - 1 and board[i][j + 1] == string[1] and not visited[i][j + 1] and self.find_res(string[1:], board, i, j + 1, visited)):
return True
visited[i][j] = False
return False

使用前缀树的方法

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Trie:
def __init__(self):
self.root = {}

def insert(self, word):
node = self.root
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['<EOW>'] = True


class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
tree = Trie()
for word in words:
tree.insert(word)
node = tree.root

rows = len(board)
cols = len(board[0])
visited = [[0] * cols for i in range(rows)]
result = []
for i in range(rows):
for j in range(cols):
if board[i][j] in node:
temp = ''
self.dfs(board, i, j, visited, node, temp, result)
return result

def dfs(self, board, i, j, visited, node, temp, result):
rows = len(board)
cols = len(board[0])

if '<EOW>' in node and temp not in result:
return result.append(temp)
if i > rows - 1 or i < 0 or j > cols - 1 or j < 0:
return
if board[i][j] not in node or visited[i][j] == 1:
return

temp += board[i][j]
visited[i][j] = 1
self.dfs(board, i + 1, j, visited, node[board[i][j]], temp, result)
self.dfs(board, i - 1, j, visited, node[board[i][j]], temp, result)
self.dfs(board, i, j + 1, visited, node[board[i][j]], temp, result)
self.dfs(board, i, j - 1, visited, node[board[i][j]], temp, result)
visited[i][j] = 0