「程序员必须掌握的算法」字典树「上篇」

朴灿烈づ我的快乐病毒、 2023-10-15 21:33 13阅读 0赞

## 「程序员必须掌握的算法」字典树「上篇」 ##

> 前言: 在计算机科学中，字典树（Trie）是一种有序树，用于保存关联数组（有时我们称之为“映射”或“字典”）。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。字典树的优势在于能够非常快速地查找、插入和删除字符串。

> 本篇文章将介绍字典树的基本概念、构建方法以及应用场景，并通过三道例题由浅入深地说明字典树的应用。

--------------------

#### 文章目录 ####

*  「程序员必须掌握的算法」字典树「上篇」
 *   *  基本概念
     *  构建方法
     *  应用场景
     *   *  例题一：查找单词
         *  例题二：查找单词前缀
         *  例题三：计算单词前缀数量
     *  总结

### 基本概念 ###

字典树是一种树形结构，典型应用是用于统计和排序大量的字符串（但不限于字符串）。它经常被搜索引擎系统用于文本词频统计。

以下是字典树的基本概念：

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

### 构建方法 ###

一个字典树的典型操作是插入一个字符串，我们可以按照以下步骤插入一个字符串：

*  从根节点开始，找到第一个字符所在的节点；
 *  如果找到对应的节点，继续寻找下一个字符；
 *  如果找不到对应的节点，创建一个新节点，将其链接到前一个节点的对应指针上，并继续寻找下一个字符。

以下是Java代码实现：

class TrieNode {
        
        public boolean isWord;
        public TrieNode[] children = new TrieNode[26];
    }
    
    class Trie {
        
        private TrieNode root;
    
        public Trie() {
        
            root = new TrieNode();
        }
    
        /** Inserts a word into the trie. */
        public void insert(String word) {
        
            TrieNode node = root;
            for (char c : word.toCharArray()) {
        
                if (node.children[c - 'a'] == null) {
        
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }
    
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
        
            TrieNode node = root;
            for (char c : word.toCharArray()) {
        
                if (node.children[c - 'a'] == null) {
        
                    return false;
                }
                node = node.children[c - 'a'];
            }
            return node.isWord;
        }
    
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
        
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
        
                if (node.children[c - 'a'] == null) {
        
                    return false;
                }
                node = node.children[c - 'a'];
            }
            return true;
        }
    }

### 应用场景 ###

字典树最常见的应用场景是字符串相关的问题，以下是三道例题由浅入深地说明字典树的应用：

#### 例题一：查找单词 ####

给定一个单词集合（如下所示），查找一个单词是否在集合中出现。

["hello", "world", "leetcode"]

以下是Java代码实现：

class Solution {
        
        public boolean findWord(String[] words, String target) {
        
            Trie trie = new Trie();
            for (String word : words) {
        
                trie.insert(word);
            }
            return trie.search(target);
        }
    }

#### 例题二：查找单词前缀 ####

给定一个单词集合（如下所示），查找一个单词是否是集合中的某个单词的前缀。

["hello", "world", "leetcode"]

以下是Java代码实现：

class Solution {
        
        public boolean findPrefix(String[] words, String target) {
        
            Trie trie = new Trie();
            for (String word : words) {
        
                trie.insert(word);
            }
            return trie.startsWith(target);
        }
    }

#### 例题三：计算单词前缀数量 ####

给定一个单词集合（如下所示），计算以某个前缀开头的单词数量。

["hello", "world", "leetcode"]

以下是Java代码实现：

class TrieNode {
        
        public int count;
        public TrieNode[] children = new TrieNode[26];
    }
    
    class Trie {
        
        private TrieNode root;
    
        public Trie() {
        
            root = new TrieNode();
        }
    
        public void insert(String word) {
        
            TrieNode node = root;
            for (char c : word.toCharArray()) {
        
                if (node.children[c - 'a'] == null) {
        
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
                node.count++;
            }
        }
    
        public int countPrefix(String prefix) {
        
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
        
                if (node.children[c - 'a'] == null) {
        
                    return 0;
                }
                node = node.children[c - 'a'];
            }
            return node.count;
        }
    }
    
    class Solution {
        
        public int countPrefix(String[] words, String prefix) {
        
            Trie trie = new Trie();
            for (String word : words) {
        
                trie.insert(word);
            }
            return trie.countPrefix(prefix);
        }
    }

在上述代码中，我们通过 `countPrefix` 方法来计算以某个前缀开头的单词数量。

### 总结 ###

本篇文章介绍了字典树的基本概念、构建方法和应用场景，并提供了三道例题由浅入深地说明字典树的应用。在实际开发中，字典树是一种非常常用的数据结构，能够帮助我们解决各种字符串相关的问题。