Tìm từ trong bảng II trong Python

Giả sử chúng ta có một bảng 2D và một danh sách các từ. Từ điển cho trước, chúng ta phải tìm tất cả các từ có trong bảng. Mỗi từ phải được xây dựng từ các chữ cái của các ô liền kề theo thứ tự (ngang hoặc dọc). Một ô không được sử dụng nhiều hơn một lần trong một từ.

Các bước giải quyết (sử dụng Trie + DFS):

• Xây dựng Trie từ danh sách từ
• Duyệt từng ô trên bảng, thực hiện DFS tìm từ trong Trie
• Đánh dấu ô đã dùng bằng ký tự đặc biệt (*), khôi phục sau khi DFS
• Khi gặp ký tự '#' trong Trie (đánh dấu cuối từ), thêm từ vào kết quả

Ví dụ

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"]))

Đầu vào

[["o","a","a","n"], ["e","t","e","a"], ["i","h","k","r"], ["i","f","l","v"]], ["oath","pea","tea","rain"]

Đầu ra

['oath', 'tea']