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

ได้รับบอร์ด 4×4 ตัวอักษร และลิสต์คำ ต้องหา จำนวนคำสูงสุด ที่สร้างได้จากเส้นทางติดกัน (8 ทิศทาง) แต่ละเซลล์ใช้ได้สูงสุด 1 ครั้งต่อคำ (แต่ใช้ซ้ำได้สำหรับคำคนละคำ)

ตัวอย่าง

m b f d
x a y a
t z t r
s q q q

words = ["bat", "far", "mat"] → Output: 3 (สร้างได้ทั้ง 3 คำ)

แนวทางแก้ปัญหา

ใช้ Trie + DFS + Backtracking:

1. สร้าง Trie จากลิสต์คำทั้งหมด
2. DFS จากทุกเซลล์บนบอร์ด:
   • ถ้าตัวอักษรอยู่ใน Trie node ปัจจุบัน → เข้าระลึก
   • Mark เซลล์visited (เช่น #)
   • ถ้าพบ end-of-word (*) → นับ +1, ลบ mark * (ป้องกันนับซ้ำ)
   • Backtrack: restore ตัวอักษร

การใช้งาน (Python)

class Solution:
    def solve(self, board, words):
        N, M = len(board), len(board[0])
        
        # Build Trie
        trie = {}
        for word in words:
            node = trie
            for c in word:
                node = node.setdefault(c, {})
            node['*'] = True
        
        ans = 0
        
        def dfs(x, y, node):
            nonlocal ans
            if '*' in node:
                del node['*']
                ans += 1
            
            temp = board[x][y]
            board[x][y] = '#'
            
            for dx in (-1, 0, 1):
                for dy in (-1, 0, 1):
                    if dx == 0 and dy == 0:
                        continue
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < N and 0 <= ny < M and board[nx][ny] in node:
                        dfs(nx, ny, node[board[nx][ny]])
            
            board[x][y] = temp
        
        for i in range(N):
            for j in range(M):
                if board[i][j] in trie:
                    dfs(i, j, trie[board[i][j]])
        
        return ans

# ทดสอบ
ob = Solution()
board = [
    ["m","b","f","d"],
    ["x","a","y","a"],
    ["t","z","t","r"],
    ["s","q","q","q"]
]
print(ob.solve(board, ["bat", "far", "mat"]))  # Output: 3

ความซับซ้อน

• Time Complexity: O(N×M×4^L) โดย L = ความยาวคำสูงสุด (ปรับปรุงได้ด้วย Trie pruning)
• Space Complexity: O(Total chars in words) สำหรับ Trie