ค้นหาคำใน Python

สมมติว่าเรามีกระดาน 2 มิติและคำศัพท์ เราต้องค้นหาว่ามีคำนั้นอยู่ในตารางหรือไม่ คำสามารถสร้างจากตัวอักษรของเซลล์ที่อยู่ติดกันตามลำดับ เซลล์ "ที่อยู่ติดกัน" คือเซลล์ที่อยู่ใกล้เคียงในแนวนอนหรือแนวตั้ง เราไม่ควรใช้เซลล์ตัวอักษรเดียวกันมากกว่าหนึ่งครั้ง ดังนั้นหากเมทริกซ์เป็นเหมือน −

คำที่กำหนดจะพูดว่า "ABCCED" คำตอบจะเป็นจริง สำหรับคำว่า "SEE" จะเป็นจริง แต่สำหรับ "ABCB" ถ้าเป็นเท็จ

ให้เราดูขั้นตอน -

• เราจะแก้ปัญหานี้โดยใช้วิธีการแบบเรียกซ้ำ ดังนั้นหากชื่อเมธอดแบบเรียกซ้ำเรียกว่า find() จะใช้เมทริกซ์ mat, word, row, col และ index i เริ่มแรกดัชนี i =0
• ถ้า i =ความยาวของคำ ให้คืนค่า True
• ถ้าแถว>=จำนวนแถวของ mat หรือแถว <0 หรือ col>=จำนวน col ของ mat หรือ col <0 หรือ word[i] ไม่เหมือนกับ mat[row, col] ให้คืนค่าเท็จ
• mat[row, col] :=“*”
• res :=find(mat, word, row + 1, col, i + 1) or find(mat, word, row - 1, col, i+1) หรือ find(mat, word, row, col + 1, i + 1) หรือ find(mat, word, row, col - 1, i + 1)
• mat[row, col] :=word[i]
• ผลตอบแทน
• งานหลักจะดำเนินการเช่น -
• n :=จำนวนแถวและ m :=จำนวนคอลัมน์
• สำหรับฉันอยู่ในช่วง 0 ถึง n
  • สำหรับ j ในช่วง 0 ถึง m
    • ถ้า word[0] =mat[i, j]
      • ถ้า find(mat, word, i, j) ไม่ใช่เท็จ ให้คืนค่า true

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

โซลูชันคลาส (วัตถุ):def มีอยู่ (ตัวเอง, บอร์ด, คำ):n =len(บอร์ด) m =len(บอร์ด[0]) สำหรับฉันในช่วง (n):สำหรับ j ในช่วง (ม.):if word[0] ==board[i][j]:if self.find(board,word,i,j):return True return False def find(ตัวเอง กระดาน คำ แถว col,i=0) :if i==len(word):return True if row>=len(board) or row <0 or col>=len(board[0]) or col<0 or word[i]!=board[row] [col]:return กระดานเท็จ[row][col] ='*' res =self.find(board,word,row+1,col,i+1) or self.find(board,word,row-1, col,i+1) หรือ self.find(board,word,row,col+1,i+1) หรือ self.find(board,word,row,col-1,i+1) board[row][col ] =คำ[i] return resob1 =Solution()print(ob1.exist([["A","B","C","E"],["S","F","C", "S"],["A","D","E","E"]],"SEE"))

อินพุต

ผลลัพธ์

จริง