数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python中的单词搜索II
假设我们有一个二维棋盘和一个单词列表。我们需要从字典中在棋盘上找到所有单词。每个单词必须由顺序相邻单元格的字母构成，其中相邻单元格是指水平或垂直相邻的单元格。需要注意的是，同一个单元格的字母在一个单词中不能使用多次。
如果输入如下：
为了解决这个问题，我们将遵循以下步骤：
创建一个数组result
定义一个名为solve()的方法，它将接收棋盘board、字典d、行号i、列号j和已匹配字符串s作为参数。
如果i或j分别不在棋盘的行和列范围内，则返回false。
l := board[i, j]
如果l存在于d中，则
d := d[l]，将l与s连接。
如果'#'在d中且d['#']不为空，则
将s插入result中。
设置d['#'] := 0
board[i, j] := '*'
如果i+1小于棋盘的行数且board[i + 1, j]在d中，则
调用solve(board, d, i + 1, j, s)
如果j+1小于棋盘的列数且board[i, j+1]在d中，则
调用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中，则
调用solve(board, d, i, j-1, s)
board[i, j] := l
定义一个名为insert()的方法，它将接收单词word和字典t作为参数。
current := t
对于word中的每个字符i
如果i不在current中，则current[i] := new map
current := current[i]
current['#'] := 1
在主方法中执行以下操作：
创建一个map t
对于words中的每个单词：调用insert(word, t)
对于棋盘board中的每个单元格i, j：调用solve(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']
浏览量：557
