LeetCode 题集：字典树

本文介绍 LeetCode 题集中，有关字典树的问题。

本题是基本的字典树问题，使用 Python 语言中的字典类型实现比较方便。

代码如下：

class Trie:

    def __init__(self):
        self.trie = {}

    def insert(self, word: str) -> None:
        cur = self.trie
        for c in word:
            if c not in cur.keys():
                cur[c] = {}
            cur = cur[c]
        cur['$'] = True

    def search(self, word: str) -> bool:
        cur = self.trie
        for c in word:
            if c not in cur.keys():
                return False

            cur = cur[c]

        return '$' in cur.keys()  # word must be the end of the tree, not just "start with"

    def startsWith(self, prefix: str) -> bool:
        cur = self.trie
        for c in prefix:
            if c not in cur.keys():
                return False

            cur = cur[c]

        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

运行效果：

本题与前一题相似，区别在于任意字符的匹配。

代码如下：

class WordDictionary:

    def __init__(self):
        self.dictionary = {}

    def addWord(self, word: str) -> None:
        cur = self.dictionary
        for c in word:
            if c not in cur.keys():
                cur[c] = {}
            cur = cur[c]
        cur['$'] = {}  # can't be True like LeetCode 208, need to be iterable

    def search(self, word: str) -> bool:
        def rec(dic: Dict, i: int):  # recursion function
            if i == len(word):
                return '$' in dic.keys()

            if word[i] == '.':
                for letter in dic.keys():
                    if rec(dic=dic[letter], i=i + 1):
                        return True
                return False

            elif word[i] not in dic.keys():
                return False

            else:
                return rec(dic=dic[word[i]], i=i + 1)

        return rec(dic=self.dictionary, i=0)



# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

运行效果：

本题的思路，把单词列表写成字典树，然后在字母矩阵的不同路径的每个位置搜索是否存在当前单词。

代码如下：

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # create a trie
        dictionary = {}
        for word in words:
            dic = dictionary
            for c in word:
                if c not in dic.keys():
                    dic[c] = {}
                dic = dic[c]
            dic['$'] = True

        res = []

        m, n = len(board), len(board[0])

        def dfs(row: int, column: int, dic: Dict, path: str):
            if '$' in dic.keys() and path not in res:
                res.append(path)

            mat_visit[row][column] = True

            if row:
                if not mat_visit[row - 1][column] and board[row - 1][column] in dic.keys():
                    dfs(row=row - 1, column=column, dic=dic[board[row - 1][column]], path=path + board[row - 1][column])
                    mat_visit[row - 1][column] = False

            if row < m - 1:
                if not mat_visit[row + 1][column] and board[row + 1][column] in dic.keys():
                    dfs(row=row + 1, column=column, dic=dic[board[row + 1][column]], path=path + board[row + 1][column])
                    mat_visit[row + 1][column] = False

            if column:
                if not mat_visit[row][column - 1] and board[row][column - 1] in dic.keys():
                    dfs(row=row, column=column - 1, dic=dic[board[row][column - 1]], path=path + board[row][column - 1])
                    mat_visit[row][column - 1] = False

            if column < n - 1:
                if not mat_visit[row][column + 1] and board[row][column + 1] in dic.keys():
                    dfs(row=row, column=column + 1, dic=dic[board[row][column + 1]], path=path + board[row][column + 1])
                    mat_visit[row][column + 1] = False

        for i in range(m):
            for j in range(n):
                mat_visit = [[False for _ in range(n)] for _ in range(m)]
                if board[i][j] in dictionary.keys():
                    dfs(row=i, column=j, dic=dictionary[board[i][j]], path=board[i][j])

        return res

运行效果：