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

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

#程序员必须掌握哪些算法?#

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

前言: 在计算机科学中,字典树(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 方法来计算以某个前缀开头的单词数量。

总结

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

相关文章
|
1月前
|
负载均衡 监控 算法
每个程序员都应该知道的 6 种负载均衡算法
每个程序员都应该知道的 6 种负载均衡算法
95 2
|
2月前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
41 1
|
3月前
|
算法 搜索推荐 程序员
程序员常用算法详细讲解
每一种算法都有其适用场景,了解并熟悉这些常用算法的策略和实现,对于解决实际编程问题具有重要的意义。需要注意的是,理论知识的重要性虽然不言而喻,但真正的理解和掌握,还需要在实践中不断地尝试和错误,以达到深入理解的目的。
28 1
|
3月前
|
机器学习/深度学习 算法 搜索推荐
程序员必须掌握的算法
作为一名程序员,掌握一些重要的算法是必不可少的。算法是解决问题的方法和步骤,对于程序员来说,熟悉和掌握一些常见的算法可以提高编程能力,解决复杂的计算问题。与此同时,算法是计算机科学中的核心概念,对于程序员来说,掌握一些基本的算法是非常重要的。
50 1
|
5月前
|
算法 程序员
程序员必知:XGB算法梳理
程序员必知:XGB算法梳理
29 0
|
5月前
|
算法 JavaScript 程序员
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
32 0
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。