王清欢Randy 王清欢Randy
首页
  • 编程语言

    • C/C++ 学习笔记
    • Golang 学习笔记
  • 算法分析

    • LeetCode 刷题笔记
  • 操作系统

    • Linux 基础
    • Vim 实用技巧
    • Shell 脚本编程
    • GDB 学习笔记
  • 开发工具

    • Git 学习笔记
  • 分布式理论

    • 共识算法
    • 分布式事务
  • 数据库内核

    • PostgreSQL
    • Postgres-XL
  • hidb
  • pgproxy
  • 实用技巧
  • 学习方法
  • 资源分享
GitHub (opens new window)
首页
  • 编程语言

    • C/C++ 学习笔记
    • Golang 学习笔记
  • 算法分析

    • LeetCode 刷题笔记
  • 操作系统

    • Linux 基础
    • Vim 实用技巧
    • Shell 脚本编程
    • GDB 学习笔记
  • 开发工具

    • Git 学习笔记
  • 分布式理论

    • 共识算法
    • 分布式事务
  • 数据库内核

    • PostgreSQL
    • Postgres-XL
  • hidb
  • pgproxy
  • 实用技巧
  • 学习方法
  • 资源分享
GitHub (opens new window)
  • 基础算法

    • 双指针

      • 双指针基础
      • 碰撞指针
      • 快慢指针
      • 滑动窗口
    • 二分查找

      • 基础应用
      • 边界收缩
      • 局部有序
    • 排序算法

      • 01八大排序
      • 02快速排序
      • 03归并排序
      • 04桶排序
      • 05堆排序
    • 优先搜索

      • 01递归
      • 02网格结构深度优先搜索
      • 03树结构深度优先搜索
      • 04图结构深度优先搜索
      • 05网格结构广度优先搜索
      • 06树结构广度优先搜索
      • 07图结构广度优先搜索
    • 回溯算法

      • 01递归
      • 02 子集问题
      • 03 全排列问题
      • 04 组合问题
      • 05 回溯搜索问题
  • 基础数据结构

    • 线性表与哈希表

      • 01数组
      • 02栈和队列
      • 03单调栈
      • 04优先队列
      • 05双端队列
      • 06哈希表
      • 07多重集合
      • 08前缀和
      • 09数据结构设计
    • 字符串

      • 01字符串比较
      • 02回文字符串
      • 03字符串匹配
      • 04字符串算术表达式
    • 单链表

      • 01链表基础操作
      • 02链表遍历
    • 二叉树

      • 01二叉树的属性
      • 02二叉树的操作
      • 03层次遍历
      • 04前中后序遍历
      • 05二叉搜索树的属性
      • 06二叉搜索树的操作
      • 07字典树
        • 05 字典树
          • 208 实现 Trie (前缀树)
          • 820 单词的压缩编码
      • 08二叉搜索树BST
    • 图

      • 01二分图
      • 02拓扑排序
      • 03并查集
      • 04最小生成树
      • 05最短路径
  • 进阶算法

    • 贪心算法

      • 01跳跃游戏
      • 02分配问题
      • 03区间问题
    • 分治策略

    • 动态规划

      • 01一维动态规划
      • 02二维动态规划
      • 03分割型动态规划
      • 04子序列问题
      • 05背包问题
      • 06字符串编辑问题
      • 07股票交易问题
  • 其他内容

    • 数学问题

      • 01公倍数与公因数
      • 02质数问题
      • 03进制转换问题
      • 04数字字符串求和问题
      • 05众数问题
      • 06中位数问题
      • 07数字处理问题
      • 08随机数问题
    • 位运算

      • 01位运算基础
      • 02妙用异或运算
      • 03二进制特性
  • LeetCode刷题笔记
  • 基础数据结构
  • 二叉树
王清欢
2023-03-24
目录

07字典树

# 05 字典树

​ 字典树一般用于判断字符串是否存在或者是否具有某种字符串前缀。如下图一个字典树中,存储了 A、to、tea、ted、ten、i、in 和 inn,以及它们的频率。

Trie

​ 为什么需要用字典树解决这类问题呢?假如我们有一个储存了近万个单词的字典,即使我们使用哈希,在其中搜索一个单词的实际开销也是非常大的,且无法轻易支持搜索单词前缀。然而由于一个英文单词的长度 n 通常在 10 以内,如果我们使用字典树,则可以在 O(n)——近似 O(1)的时间内完成搜索,且额外开销非常小。

# 208 实现 Trie (前缀树) (opens new window)

尝试建立一个字典树,支持快速插入单词、查找单词、查找单词前缀的功能

以下是数据结构的调用样例

输入: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] 输出: [null, null, true, false, true, null, true]

解释: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch : prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

public:
    Trie() : children(26), isEnd(false) {}

    void insert(string word) {
        Trie* node = this;
        for (char ch : word) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }

    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr;
    }
};

# 820 单词的压缩编码 (opens new window)

​ 单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成,且满足:

  • words.length == indices.length
  • 助记字符串 s 以 '#' 字符结尾
  • 对于每个下标 indices[i] ,s 的一个从 indices[i] 开始、到下一个 '#' 字符结束(但不包括 '#')的 子字符串 恰好与 words[i] 相等

​ 给定一个单词数组 words ,返回成功对 words 进行编码的最小助记字符串 s 的长度 。

输入:words = ["time", "me", "bell"]

输出:10

解释:一组有效编码为 s = "time#bell#" 和 indices = [0, 2, 5] 。 words[0] = "time" ,s 开始于 indices[0] = 0 到下一个 '#' 结束的子字符串,如加粗部分所示 "time#bell#" words[1] = "me" ,s 开始于 indices[1] = 2 到下一个 '#' 结束的子字符串,如加粗部分所示 "time#bell#" words[2] = "bell" ,s 开始于 indices[2] = 5 到下一个 '#' 结束的子字符串,如加粗部分所示 "time#bell#"

解析:

class Trie{
private:
    Trie* child[26];
    bool found;
public:
    Trie(){
        for(int i=0;i<26;++i){
            child[i] = nullptr;
            found = false;
        }
    }

    void insert(string word){
        Trie* node = this;
        for(const auto ch:word){
            if(node->child[ch-'a'] == nullptr){
                node->child[ch-'a'] = new Trie();
            }
            node = node->child[ch-'a'];
        }
        node->found = true;
    }

    bool search(string word){
        Trie* node = this;
        for(const auto ch:word){
            if(node->child[ch-'a']==nullptr){
                return false;
            }
            node = node->child[ch-'a'];
        }
        return node->found;
    }

    bool prefix(string prefix){
        Trie* node = this;
        for(const auto ch:prefix){
            if(node->child[ch-'a']==nullptr){
                return false;
            }
            node = node->child[ch-'a'];
        }
        return true;
    }
};

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> hash;
        // 要从长单词到短单词构建字典树
        sort(words.begin(),words.end(),[](string& a, string& b){
            return a.length() > b.length();
        });
        Trie* trie = new Trie();
        // 遍历所有单词,如果已经存在字典树中则直接跳过,反之生成插入新单词
        for(string& word:words){
            reverse(word.begin(),word.end()); // 后缀检验和插入
            if(trie->prefix(word)){
                continue;
            }
            trie->insert(word);
            hash.insert(word);
        }

        // 计算字典树中表征的单词个数
        int ans = 0;
        for(auto word:hash){
            ans += word.length()+1;
        }
        return ans;
    }
};
上次更新: 2023/11/19, 12:55:48
06二叉搜索树的操作
08二叉搜索树BST

← 06二叉搜索树的操作 08二叉搜索树BST→

Theme by Vdoing | Copyright © 2023-2024 Wang Qinghuan | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式