Python中的Word Search II
假设我们有一个二维板和一个单词列表。因此，从字典中，我们必须在黑板上找到所有单词。在这里，每个单词必须由顺序相邻的单元格的字母构成，其中相邻单元格是水平或垂直相邻的单元格。我们必须谨记，同一字母单元在一个单词中不能多次使用。
所以如果输入像-
为了解决这个问题，我们将遵循以下步骤-
制作数组结果
定义一个名为的方法solve()，它将使用boardd，i，js
当i或j分别不在板的行和列范围内时，返回false
l：=board[i，j]
如果d中存在l，则
调用solve(board,d,i,j-1,s)
调用solve(board,d,i-1,j,s)
调用solve（board，d，i，j+1，s）
调用solve（board，d，i+1，j，s）
将s插入结果
设置d[#]：=0
d：=d[l]，将l与s连接
如果#在d中并且d[#]不为null，则
板[i，j]：=*
如果i+1<d中板和板[i+1，j]的行数，则
如果j+1<d中board和board[i，j+1]中的列数，则
如果i-1>0并在d中放置[i-1，j]，则
如果j-1>0并在d中放置board[i，j-1]，则
board[i，j]：=l
定义一个称为的方法insert()，它将采用单词和字典t
当前：=t
对于我来说
如果我不在当前状态，那么current[i]：=新映射
当前：=当前[i]
当前[#]：=1
从主要方法中执行以下操作-
创建映射
对于单词中的单词：调用insert(word,t)
对于板中的每个单元i，j-调用resolve(board,t,i,j)
返回结果
示例
让我们看下面的实现以更好地理解-
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']