题目分析

在三面字节的时候撕过这个算法，之前没有遇到这个题目，虽然撕出来了，但是效率相对较低，在第一种解法中列举了我当时的代码，然后会给出一个更优化的版本提供小伙伴们学习。

前缀树

我们按照题目的思路进行思考，以示例为参考，画一个Trie树。

每一个节点都有两个属性，一个是该节点代表的字符，一个是该节点的孩子。因此一个简单的想法就是创建一个数据结构，其中包括val和child两个属性。val是字符串，child是孩子的集合。

插入时：看当前节点的孩子中，有没有val等于该字符的，如果有则递归寻找下一个字符，如果没有，则需要递归创建一条新的路径。注意在最后要加入终止字符，说明有这个单词出现。如apple单词，这时查找app也可以查到，但是加入了终止位以后，查到app时还要判断后面是否有终止位，就无法查到app单词了。**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

查找单词时：看当前节点的孩子中，有没有val等于该字符的，如果有则递归寻找下一个字符，如果没有，则直接返回False。当所有字符都找到后，还需要查找终止位，如果有终止位，则说明查到了，否则没有查到。**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

查找前缀时：和查找单词类似，只不过不用查找终止位，如果所有字符都查到则返回True即可。**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.child = set()


class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = TreeNode(None)


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self.dic
        for c in word:
            for node in cur.child:
                if node and c == node.val:
                    cur = node
                    break
            else:
                new_node = TreeNode(c)
                cur.child.add(new_node)
                cur = new_node
        cur.child.add(None)


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        cur = self.dic
        for c in word:
            for node in cur.child:
                if node and c == node.val:
                    cur = node
                    break
            else:
                return False
        return None in cur.child


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        cur = self.dic
        for c in prefix:
            for node in cur.child:
                if node and c == node.val:
                    cur = node
                    break
            else:
                return False
        return True

优化前缀树

优化前缀树思路也非常简单，介绍一下就可以知道。Trie树可以看成一个字典，键就是节点的字符，值就是节点的孩子。因此不需要创建额外的类型，直接使用字典即可。

插入，查找的思路和前缀树相同，但是在字典中查找速度比遍历孩子节点更加迅速，代码量也更加简洁，这里就不过多介绍，直接看代码即可。

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = dict()


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        cur = self.dic
        for c in word:
            if c not in cur:
                cur[c] = {}
            cur = cur[c]
        cur['#'] = 1


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        cur = self.dic
        for c in word:
            if c not in cur:
                return False
            cur = cur[c]
        return True if '#' in cur else False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        cur = self.dic
        for c in prefix:
            if c not in cur:
                return False
            cur = cur[c]
        return True

下面给出Java语言的前缀树实现，其实逻辑是一样的，但是不用map表示，用更常见的数组即可，数组的第m位就表示字符’a’ + m。

class Trie {
    private static final int ALPHA = 26;

    private Trie[] children = new Trie[ALPHA];

    private boolean isEnd = false;

    public Trie() {
    }

    public void insert(String word) {
        Trie cur = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) {
                cur.children[idx] = new Trie();
            }
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Trie cur = this;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) {
                return false;
            }
            cur = cur.children[idx];
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        Trie cur = this;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) {
                return false;
            }
            cur = cur.children[idx];
        }
        return cur != null;
    }
}

刷题总结

Trie树有很多经典的应用，如搜索引擎的自动补全机制，word中的拼写检查机制，手机九宫格打字预测等等。在许多算法题中trie树也称为前缀树，字典树，对于字符串匹配等问题可能有巧妙求解方法。