โปรแกรมนับจำนวนคำที่เราสร้างได้จากเมทริกซ์ของตัวอักษรใน Python

สมมติว่าเรามีกระดานตัวอักษรขนาด 4 x 4 และรายการคำ เราต้องหาจำนวนคำมากที่สุดที่สามารถสร้างในกระดานได้ตามลำดับตัวอักษรที่อยู่ติดกัน โดยใช้เซลล์สูงสุดหนึ่งครั้งต่อคำ (แต่เรา สามารถใช้เซลล์ซ้ำสำหรับคำอื่น ๆ ได้) เราขึ้น ลง ซ้าย ขวา หรือแนวทแยงก็ได้

ดังนั้นหากอินพุตเป็นแบบ

word =["bat", "far", "mat"] จากนั้นผลลัพธ์จะเป็น 3 เนื่องจากเราสามารถสร้าง mat [0,1] → [1,1] → [2,0] bat [0, 2] → [1,1] → [2,2] และไกล [0,2] → [1,3] → [2,3]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• N :=จำนวนแถวของ A, M :=จำนวนคอลัมน์ที่มีขนาด A

• ลอง :=แผนที่ใหม่

• สำหรับแต่ละคำในคำ ทำ

  • ปัจจุบัน :=ลอง

  • สำหรับแต่ละ c ใน word ทำ

    • ถ้า c เป็นปัจจุบัน แล้ว

      • ปัจจุบัน :=ปัจจุบัน[c]

    • มิฉะนั้น

      • ปัจจุบัน[c] :=แผนที่ใหม่

      • ปัจจุบัน :=ปัจจุบัน[c]

  • ปัจจุบัน["*"] :=จริง

• ตอบ :=0

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา x, y, d

• ถ้า "*" อยู่ใน d แล้ว

  • ลบ d["*"]

  • ans :=ans + 1

• อุณหภูมิ :=A[x, y]

• A[x, y] :="#"

• สำหรับแต่ละรายการ i ใน [x - 1, x, x + 1] ทำ

  • สำหรับแต่ละรายการ j ใน [y - 1, y, y + 1] ทำ

    • ถ้า i และ j อยู่ในช่วงของเมทริกซ์ และ A[i, j] อยู่ใน d แล้ว

      • dfs(i, j, d[A[i, j]])

• A[x, y] :=อุณหภูมิ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• สำหรับผมอยู่ในช่วง 0 ถึง N ทำ

  • สำหรับ j ในช่วง 0 ถึง M ให้ทำ

    • ถ้า A[i][j] อยู่ในช่วงทดลองแล้ว

      • dfs(i, j, พยายาม[A[i, j]])

• กลับมาอีกครั้ง

ตัวอย่าง (Python)

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

class Solution:
   def solve(self, A, words):
      N = len(A)
      M = len(A[0])
      trie = dict()
      for word in words:
         current = trie
         for c in word:
            if c in current:
               current = current[c]
            else:
               current[c] = dict()
               current = current[c]
         current["*"] = True
      ans = 0
      def dfs(x, y, d):
         nonlocal ans
         if "*" in d:
            del d["*"]
            ans += 1
         temp = A[x][y]
         A[x][y] = "#"
         for i in [x - 1, x, x + 1]:
            for j in [y - 1, y, y + 1]:
               if 0 <= i < N and 0 <= j < M and A[i][j] in d: dfs(i, j, d[A[i][j]])
         A[x][y] = temp
      for i in range(N):
         for j in range(M):
            if A[i][j] in trie:
               dfs(i, j, trie[A[i][j]])
      return ans
ob = Solution()
matrix = [
   ["m", "b", "f", "d"],
   ["x", "a", "y", "a"],
   ["t", "z", "t", "r"],
   ["s", "q", "q", "q"]
]
words = ["bat", "far", "mat"]
print(ob.solve(matrix, words))

อินพุต

[
["m", "b", "f", "d"],
["x", "a", "y", "a"],
["t", "z", "t", "r"],
["s", "q", "q", "q"] ],
["bat", "far", "mat"]

ผลลัพธ์

3