Python 中的单词搜索 II
假设我们有一个 2D 棋盘和一个单词列表。因此，我们必须从字典中找出棋盘中的所有单词。这里每个单词必须由连续相邻单元格的字母构成，其中相邻单元格是水平或垂直相邻的单元格。我们必须记住，同一个字母单元格不能在一个单词中使用多次。
因此，如果输入类似 −
要解决这个问题，我们将遵循以下步骤 −
生成一个数组结果
定义一个名为solve()的方法，它将获取board、d、i、j s
当i或j分别不在board行和列范围内时，返回false
l := board[i, j]
如果l存在于d中，则
d := d[l]，将l与s连接起来
如果#在d中并且d[#]不为空，然后
将 s 插入结果中
set d[#] := 0
board[i, j] := *
如果 i+1 < 棋盘中的行数且 d 中的 board[i + 1, j] 为棋盘，则
调用solve(board, d, i + 1, j, s)
如果 j+1 < 棋盘中的列数且 d 中的 board[i, j+1] 为棋盘，则
调用solve(board, d, i, j+1, s)
如果 i-1 > 0 且 board[i - 1, j] 在 d 中，则
调用solve(board, d, i - 1, j, s)
如果 j-1 > 0 且 board[i, j-1] 在 d 中，则
call solve(board, d, i, j-1, s)
board[i, j] := l
定义一个名为 insert() 的方法，该方法将获取单词和字典 t
current := t
for i in word
如果 i 不在 current 中，则 current[i] := new map
current := current[i]
current[#] := 1
从 main 方法执行以下操作 −
创建一个 map t
for word in words:调用 insert(word, t)
对于 board 中的每个单元格 i、j − 调用 resolve(board, t, i, j)
返回 result
示例
让我们看看下面的实现以便更好地理解 −
class Solution(object):
def findWords(self, board, words):
self.result = []
t = {}
for word in words:
self.insert(word,t)
for i in range(len(board)):
for j in range(len(board[0])):
self.solve(board,t,i,j)
return self.result
def solve(self,board,d,i,j,s=""):
if i<0 or j<0 or i>=len(board) or j>=(len(board[0])):
return
l = board[i][j]
if l in d:
d = d[l]
s+=l
if "#" in d and d['#']:
self.result.append(s)
d['#'] = 0
board[i][j] = '*'
if i+1<len(board) and board[i+1][j] in d :
self.solve(board,d,i+1,j,s)
if j+1 < len(board[0]) and board[i][j+1] in d:
self.solve(board,d,i,j+1,s)
if i-1>=0 and board[i-1][j] in d :
self.solve(board,d,i-1,j,s)
if j-1>=0 and board[i][j-1] in d :
self.solve(board,d,i,j-1,s)
board[i][j] = l
def insert(self, word,t):
current = t
for i in word:
if i not in current:
current[i] = {}
current =current[i]
current['#']=1
ob = Solution()
print(ob.findWords([["o","a","a","n"],["e","t","e","a"],["i","h","k", "r"],["i","f","l","v"]],["oath","pea","tea","rain"]))
输入
[["o","a","a","n"], ["e","t","e","a"], ["i","h","k","r"], ["i","f","l","v"]], ["oath","pea","tea","rain"]
输出
['oath', 'tea']
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
