Эффективность соответствия Trie tree в поиске слов

Я отлаживаю несколько подобных решений, но задаюсь вопросом, можем ли мы улучшить Trie Tree до префикса частичного совпадения (в методе поиска класса Trie, текущий метод поиска проверяет только совпадение полного слова или нет) даже повысить производительность, который может вернуться с неправильного пути раньше? Я не очень уверен в этой идее, поэтому ищите совета раньше.

Я размещаю одно из подобных решений. Спасибо.

---

Учитывая двумерную доску и список слов из словаря, найдите все слова на доске.

Каждое слово должно быть построено из букв последовательно соседней ячейки, где "смежные" ячейки являются горизонтальными или вертикальными соседями. Одна и та же ячейка письма не может использоваться более одного раза в слове.

Например, С учетом слов = ["oath","pea","eat","rain"] и board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Возвращение [ "есть", "клятва" ]

class TrieNode():
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.isWord = False

class Trie():
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for w in word:
            node = node.children[w]
        node.isWord = True

    def search(self, word):
        node = self.root
        for w in word:
            node = node.children.get(w)
            if not node:
                return False
        return node.isWord

class Solution(object):
    def findWords(self, board, words):
        res = []
        trie = Trie()
        node = trie.root
        for w in words:
            trie.insert(w)
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                self.dfs(board, node, i, j, "", res)
        return res

    def dfs(self, board, node, i, j, path, res):
        if node.isWord:
            res.append(path)
            node.isWord = False
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):
            return 
        tmp = board[i][j]
        node = node.children.get(tmp)
        if not node:
            return 
        board[i][j] = "#"
        self.dfs(board, node, i+1, j, path+tmp, res)
        self.dfs(board, node, i-1, j, path+tmp, res)
        self.dfs(board, node, i, j-1, path+tmp, res)
        self.dfs(board, node, i, j+1, path+tmp, res)
        board[i][j] = tmp