前缀树

前缀树(trie)又被称为字典树，是一种树形结构，是哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

它有3个基本性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。

下图即为一个前缀树的示例。

trie.jpg

下面首先通过一个例子来了解前缀树。

LeetCode 208. 实现 Trie (前缀树)

内容简述：实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

Python代码：

# 定义前缀树节点
class TrieNode:
    def __init__(self, c):
        self.val = c # 字符
        self.next = {} # 子节点字典
        self.isEnd = False # 是否单词结尾

# 定义前缀树
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode(' ') # 定义根节点


    def insert(self, word):
        """
        Inserts a word into the trie.
        """
        current = self.root 
        for i in range(len(word)): # 遍历单词
            flag = False
            if word[i] not in current.next:
                trieNode = TrieNode(word[i])
                current.next[word[i]] = trieNode
                current = trieNode
            else:
                current = current.next[word[i]]
  
        current.isEnd = True

    def search(self, word):
        """
        Returns if the word is in the trie.
        """
        current = self.root
        for i in range(len(word)):
            if word[i] not in current.next:
                return False
            current = current[word[i]]
            if i == len(word) - 1:
                if not current.isEnd:
                    return False
        return True

    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        current = self.root
        for i in range(len(prefix)):
            if prefix[i] not in current.next:
                return False
            else:
                current = current.next[prefix[i]]
            if not flag:
                return False
        return True

LeetCode 212. 单词搜索 II

内容简述：给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。

解题思路：本题主要利用前缀树和回溯算法

Python代码

 def findWords(board, words):
      # 前缀树，这里使用多重字典实现
        trie = {}
        for word in words:
            current = trie
            for ele in word:
                current = current.setdefault(ele, {})
            current['end'] = word  # end代表结束，并标记整个单词
        
        # 访问矩阵，记录每个点是否已访问
        visited = [[False for _ in range(len(board[0]))] for _ in range(len(board))]

        # 结果集合
        result = set()
        # 回溯遍历，使用深度优先搜索
        def dfs(i, j, trieNode):
            # 排除不能使用的节点
            if i < 0 or i >= len(board):
                return
            elif j < 0 or j >= len(board[0]):
                return
            if visited[i][j]:
                return
            # 是否在前缀树中
            if board[i][j] in trieNode:
                visited[i][j] = True
                if 'end' in trieNode[board[i][j]]: # 是结束单词
                    result.add(trieNode[board[i][j]]['end'])
                # 依次遍历四周节点
                dfs(i - 1, j, trieNode[board[i][j]])
                dfs(i + 1, j, trieNode[board[i][j]])
                dfs(i, j - 1, trieNode[board[i][j]])
                dfs(i, j + 1, trieNode[board[i][j]])

                visited[i][j] = False
        # 遍历单词列表
        for i in range(len(board)):
            for j in range(len(board[i])):
                dfs(i, j, trie)

        return list(result)

LeetCode 422 数组中两个数的最大异或值

内容简述：给定一个非空数组，求数组中两个元素异或的最大值。

解题思路：构造一个只有0和1的前缀树，让每个元素去和前缀树构造最大值，最后选出最大的最大值就行。

 def findMaximumXOR(nums) :
        # 生成二进制数组
        a = []
        for num in nums:
            a1 = []
            for i in range(32):
                a1.append(num >> i & 1)
            a.append(a1[::-1])
        
        # 前缀树
        trie = {}
        for ele in a:
            current = trie
            for e in ele:
                current = current.setdefault(e, {})
        # 查找最大值的函数
        def search(ele):
            current = trie
            r = 0
            for i in range(len(ele)):
                c = 1 - ele[i]
                if c in current: # 1和0 异或为1最大
                    r = (r << 1) + 1
                    current = current[c]
                else: # 没有就只能异或成0
                    r = r << 1
                    current = current[ele[i]]
            return r

        # 遍历求出最大的结果
        max_value = -1
        for ele in a:
            result = search(ele)
            print(result)
            if result > max_value:
                max_value = result
        return max_value