「程序员必须掌握的算法」字典树「上篇」
前言: 在计算机科学中,字典树(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"] • 1
以下是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
方法来计算以某个前缀开头的单词数量。
总结
本篇文章介绍了字典树的基本概念、构建方法和应用场景,并提供了三道例题由浅入深地说明字典树的应用。在实际开发中,字典树是一种非常常用的数据结构,能够帮助我们解决各种字符串相关的问题。