資料結構
網路
關係資料庫管理系統 (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
