สมมติว่าเรามีกระดาน 2 มิติและรายการคำศัพท์ ดังนั้นจากพจนานุกรม เราจึงต้องค้นหาคำทั้งหมดในกระดาน ในที่นี้ แต่ละคำจะต้องสร้างจากตัวอักษรของเซลล์ที่อยู่ติดกันตามลำดับ โดยที่เซลล์ที่อยู่ติดกันคือเซลล์ที่อยู่ใกล้เคียงในแนวนอนหรือแนวตั้ง เราต้องจำไว้ว่าไม่สามารถใช้เซลล์ตัวอักษรเดียวกันมากกว่าหนึ่งครั้งในหนึ่งคำ
ดังนั้นหากอินพุตเป็นแบบ −
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างผลลัพธ์อาร์เรย์
-
กำหนดวิธีการที่เรียกว่า Solve() ซึ่งจะใช้ board, d, i, j s
-
เมื่อ i หรือ j ไม่อยู่ในช่วงแถวของบอร์ดและคอลัมน์ตามลำดับ ให้คืนค่าเท็จ
-
l :=board[i, j]
-
ถ้า l มีอยู่ใน d แล้ว
-
d :=d[l], เชื่อม l กับ s
-
ถ้า # อยู่ใน d และ d[#] ไม่เป็นค่าว่าง ดังนั้น
-
แทรก s ลงในผลลัพธ์
-
ตั้งค่า d[#] :=0
-
-
กระดาน[i, j] :=*
-
ถ้า i+1 <จำนวนแถวในบอร์ดและบอร์ด[i + 1, j] ใน d แล้ว
-
แก้การโทร (บอร์ด, d, i + 1, j, s)
-
-
ถ้า j+1 <จำนวนคอลัมน์ในบอร์ดและบอร์ด[i, j+1] ใน d แล้ว
-
โทรแก้(กระดาน, d, ผม, j+1, s)
-
-
ถ้า i-1> 0 และบอร์ด[i - 1, j] ใน d แล้ว
-
แก้การโทร (บอร์ด, d, i - 1, j, s)
-
-
ถ้า j-1> 0 และ board[i, j-1] ใน d แล้ว
-
โทรแก้(บอร์ด, d, ผม, j-1, s)
-
-
กระดาน[i, j] :=l
-
-
กำหนดวิธีการหนึ่งที่เรียกว่า insert() ซึ่งจะใช้คำและพจนานุกรม t
-
ปัจจุบัน :=t
-
สำหรับฉันในคำ
-
ถ้าฉันไม่ได้อยู่ในปัจจุบัน แล้ว current[i] :=แผนที่ใหม่
-
ปัจจุบัน :=ปัจจุบัน[i]
-
-
ปัจจุบัน[#] :=1
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
สร้างแผนที่ t
-
สำหรับคำในคำ:call insert(word, t)
-
สำหรับแต่ละเซลล์ i, j ในบอร์ด − call Solve(บอร์ด, 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']
