海通建设集团有限公司网站,庆阳网站设计 贝壳下拉,做网站都需要哪些费用,怎么做网站截图「程序员必须掌握的算法」字典树「上篇」 前言: 在计算机科学中#xff0c;字典树#xff08;Trie#xff09;是一种有序树#xff0c;用于保存关联数组#xff08;有时我们称之为“映射”或“字典”#xff09;。与二叉查找树不同#xff0c;键不是直接保存在节点中字典树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 方法来计算以某个前缀开头的单词数量。
总结
本篇文章介绍了字典树的基本概念、构建方法和应用场景并提供了三道例题由浅入深地说明字典树的应用。在实际开发中字典树是一种非常常用的数据结构能够帮助我们解决各种字符串相关的问题。