算法练习：字典树/前缀树 (Trie)

[ShannonChenCHN]

题目列表

• 208. 实现 Trie (前缀树) （难度中等）⭐️
• 单词查找
• 211. 添加与搜索单词 - 数据结构设计（难度中等）⭐️
• 212. 单词搜索 II（难度困难）⭐️
• 692. Top K Frequent Words（难度中等）
• leetcode刷题总结之前缀树

总结：

1. 需要掌握 Trie 的实现
   • 需要注意的是 Trie 和多叉树的区别，建议画图结合图来看。
   • 记住 208 题 的模板代码
     • 节点结构
     • 插入单词
     • 查找单词
     • 前缀匹配
2. 简单概括 Trie 的应用就是：一次建树，多次查询
   • 搜索引擎关键词输入的自动联想
   • 拼写检查
   • IP 路由地址前缀匹配
3. Trie 的性质
   • Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。
   • 查找或插入一个长度为 L 的单词，访问 next 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。
   • Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)。

[ShannonChenCHN]

延伸阅读

• swift-algorithm-club/Trie/
• Trie树 - 编程之法：面试和算法心得
• Counting the number of words in a Trie (I really recommend)
• Using Tries - TopCoder
• TRIE DATA STRUCTURE (I really recommend)
• PRINT ALL WORDS IN A TRIE DATA STRUCTURE

[ShannonChenCHN]

单词查找

一个文本文件，大约有一万行，每行一个词，要求找出该文件中是否存在某个指定的单词，请给出主要思想和时间复杂度分析。

分析

1. 定义数节点结构：首先定义一个表征 Trie 节点的数据结构，其实就是一个树的节点，每个节点包括 0~26 个子节点。
   另外，每个节点有一个变量来记录是否是叶节点。

2. 插入单词：从前往后依次遍历单词的每一个字符，每位字符对应树的每一层（根节点为空，所以根节点除外），
   如果树中对应的层中没有该字符，就在这一层中该字符对应的位置（0~25）插入一个节点

3. 打印所有单词：这里可以用先序遍历来实现，核心思路在于记录路径。
   我们可以用一个数组来保存所有的“浏览”过的路径，如果遇到一个是单词结尾字符的节点，就打印数组中的所有字符。

4. 查找单词：满足两个条件，一是单词的每个字母都有对应的节点，二是单词末尾字符对应的节点正好是单词结尾节点

示例代码

完整示例代码见这里。

#include <iostream>

/// Alphabet size (# of symbols)
#define ALPHABET_SIZE   26

/// Calucate array size
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

/// Converts key current character into index
/// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')


/// Trie node
struct TrieNode {
    TrieNode *children[ALPHABET_SIZE];
    bool isLeaf;
};


/// Returns new trie node (initialized to NULLs)
TrieNode *creatNode(void) {
    TrieNode *pNode = new TrieNode;
    pNode->isLeaf = false;
    
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        pNode->children[i] = nullptr;
    }
    
    return pNode;
}

/// If not present, inserts key into trie
/// If the key is prefix of trie node, just
/// marks leaf node
void insert(TrieNode *pRoot, const char *key) {
    // 1. get the length of the key
    int keyLength = (int)strlen(key);
    
    // 2. iterate the key string, if the character
    // is not presented in the corresponding level,
    // insert a new node.
    TrieNode *pNode = pRoot;
    for (int level = 0; level < keyLength; level++) {
        int indexOfCurrentChar = CHAR_TO_INDEX(key[level]);
        if (pNode->children[indexOfCurrentChar] == nullptr) {
            pNode->children[indexOfCurrentChar] = creatNode();
        } else {
            pNode->children[indexOfCurrentChar]->isLeaf = false;
        }
        
        pNode = pNode->children[indexOfCurrentChar];
    }
    
    // 3. Set the node that doesn't have any children as leaf.
    pNode->isLeaf = true;
    for (int index = 0; index < ALPHABET_SIZE; index++) {
        if (pNode->children[index] != nullptr) {
            pNode->isLeaf = false;
        }
    }
    
}

void printTrie(TrieNode *pRoot) {
    
    // pre-order
    for (int index = 0; index < ALPHABET_SIZE; index++) {
        TrieNode *currentNode = pRoot->children[index];
        
        if (currentNode != nullptr) {
            char rootChar = index + 'a';
            printf("%c", rootChar);
            
            if (currentNode->isLeaf) {
                printf(", ");
            } else {
                printTrie(currentNode);
            }
        }
    }
    
}

int main(int argc, const char * argv[]) {
    
    // Input keys (use only 'a' through 'z' and lower case)
    // The array used to hold input keys is two-dimensional array
    char keys[][8] = {"the", "a", "there", "answer",
        "any", "by", "bye", "their"};
    
    TrieNode *pRoot = creatNode();
    
    // Construct Trie
    for (int i = 0; i < ARRAY_SIZE(keys); i++) {
        insert(pRoot, keys[i]);
    }
    
    printTrie(pRoot);
    
    return 0;
}

延伸阅读

• Trie树 - 编程之法：面试和算法心得
• Counting the number of words in a Trie (I really recommend)
• Using Tries - TopCoder
• TRIE DATA STRUCTURE (I really recommend)
• PRINT ALL WORDS IN A TRIE DATA STRUCTURE
• swift-algorithm-club/Trie/

[ShannonChenCHN]

208. 实现 Trie (前缀树)

2021.03.27 09:00 pm ~ 2021.03.27 10:10 pm

参考：

• https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/
• https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt/
• https://leetcode.com/problems/implement-trie-prefix-tree/solution/

主要有四个环节：

1. 节点结构
2. 插入单词
3. 查找单词
4. 前缀匹配

需要注意的是 Trie 和多叉树的区别，建议画图结合图来看。

class Trie {

    class TrieNode {
        var isEnd: Bool = false
        var links: [Character: TrieNode] = [:]
    }
    var root: TrieNode = TrieNode()

    /** Initialize your data structure here. */
    init() { 

    }
    
    /** Inserts a word into the trie. */
    func insert(_ word: String) {
        var node: TrieNode = root
        for char in word {
            if node.links[char] == nil {
                node.links[char] = TrieNode()
            }
            node = node.links[char]!
        }
        node.isEnd = true
    }
    
    /** Returns if the word is in the trie. */
    func search(_ word: String) -> Bool {
        var node: TrieNode = root
        for char in word {
            if node.links[char] == nil {
                return false
            }
            node = node.links[char]!
        }

        return node.isEnd
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    func startsWith(_ prefix: String) -> Bool {
        var node: TrieNode = root
        for char in prefix {
            if node.links[char] == nil {
                return false
            }
            node = node.links[char]!
        }
        return true
    }
}

[ShannonChenCHN]

211. 添加与搜索单词 - 数据结构设计（难度中等）

解法：Trie

2021.03.27 10:10 pm ~ 10:50 pm

参考：https://leetcode.com/problems/design-add-and-search-words-data-structure/discuss/59554/My-simple-and-clean-Java-code

class WordDictionary {

    class TrieNode {
        var isEnd: Bool = false
        var links: [Character: TrieNode] = [:]
    }
    var root: TrieNode = TrieNode()

    /** Initialize your data structure here. */
    init() {

    }

    
    /** Inserts a word into the trie. */
    func addWord(_ word: String) {
        var node: TrieNode = root
        for char in word {
            if node.links[char] == nil {
                node.links[char] = TrieNode()
            }
            node = node.links[char]!
        }
        node.isEnd = true
    }
    
    /** Returns if the word is in the trie. */
    func search(_ word: String) -> Bool {
        return match(Array(word), 0, root)
    }

    func match(_ characters: [Character], _ start: Int, _ trieNode: TrieNode) -> Bool {
        // 最后一位字符
        guard start < characters.count else {
            return trieNode.isEnd
        }

        // 普通字符
        let char = characters[start]
        if char != "." {
            return trieNode.links[char] != nil && match(characters, start+1, trieNode.links[char]!)
        }

        // 通配符
        var node: TrieNode = trieNode
        for (char, nextNode) in node.links {
            if match(characters, start+1, nextNode) {
                return true
            }
        }

        return false
    } 
}

[ShannonChenCHN]

212. 单词搜索 II