当前位置：首页 > news >正文

从零备战蓝桥杯——Trie 字典树（前缀树）

news 来源：原创 2024/5/6 14:32:03

双非刷leetcode备战2023年蓝桥杯，qwq加油吧，无论结果如何总会有收获！一起加油,我是跟着英雄哥的那个思维导图刷leetcode的，大家也可以看看所有涉及到的题目用leetcode搜索就可以哦，因为避让添加外链，一起加油！！！
零基础小白也可以看，因为我就是！
请添加图片描述

文章目录

Trie 字典树（前缀树）
- - 插入
  - 找串和找串的前缀
  - 相关题目：[leetcode：208. 实现 Trie (前缀树)]
  - 相关题目：[leetcode：14. 最长公共前缀]
  - 相关题目：[LeetCode211. 添加与搜索单词 - 数据结构设计]
  - 相关题目：[820. 单词的压缩编码]

Trie 字典树（前缀树）

啥叫字典树其实就是找一个前缀相同的东西，是一个类似于树的结构，来保存一个串。

字典树的基本结构：

#include <iostream>
#include <string.h>
#include <string>
using namespace std;
class Trie
{
private:
    bool isEnd;     //判断是否为结尾
    Trie *next[26]; //保存着下一个数是26位数哪一个的地址
public:
    Trie()
    {
        isEnd=false;
        memset(next,0,sizeof(next));
    }

    
};

在这里插入图片描述

这个地方的技巧就是用一个26个字母的数组来标记26个字母哪个存在如果存在就下一个如果不存在就建一个新Trie。这个树的储存结构其实是好多个二十六个字母的Trie的地址组成的。就可以达到快速查找啊插入啊的效果。

插入

如果没有就建一个新Trie，然后下一个肯定有了，然后直接访问下一个就行了，等全访问完了就标记isEnd=true表示这个串插入完了；

 void insert(string word) //插入一个字符串
    {
        Trie *node = this;
        for (int i = 0; i < word.length(); i++)
        {
            if (node->next[word[i] - 'a'] == NULL) //如果没有就新建一个trie；
            {
                node->isEnd[word[i] - 'a'] = new Trie();
            }
            node=node->next[word[i]-'a'];//访问下一个;

        }
        node->isEnd=true;//标记这个trie结束了
    }

找串和找串的前缀

找串：

从头开始访问，如果有就下一个，如果没有就返回false。如果全访问完了，就返回isEnd；(没访问完就代表没有)

    bool search(string word)
    {
        Trie * node=this;
        for (int i = 0; i < word.length(); i++)
        {
            node =node->next[word[i]-'a'];
            if(node==NULL)
            {
                return false;
            }
        }
        retrun node->isEnd;
   	}

找串的前缀：

与找串相同不过不需要全访问完了，只要期间都有，把这个前缀访问完了就可以返回true

bool startsWith(string prefix)
    {
        Trie * node=this;
        for (int i = 0; i < word.length(); i++)
        {
            node =node->next[word[i]-'a'];
            if(node==NULL)
            {
                return false;
            }
        }
        retrun true;
    }

相关题目：[820. 单词的压缩编码]

//这个要注意要把单词少的放在后面

class Trie
{
private:
    bool isEnd;     //判断是否为结尾
    Trie *next[26]; //保存着下一个数是26位数哪一个的地址
public:
    Trie()
    {
        isEnd = false;
        memset(next, 0, sizeof(next));
    }

    void insert(string word) //插入一个字符串
    {
        Trie *node = this;
        for (int i = word.length() - 1; i >= 0; i--)
        {
            if (node->next[word[i] - 'a'] == NULL) //如果没有就新建一个trie；
            {
                node->next[word[i] - 'a'] = new Trie();
            }
            node = node->next[word[i] - 'a']; //访问下一个;
        }
        node->isEnd = true; //标记这个trie结束了
    }

    bool startsWith(string prefix)
    {
        Trie *node = this;
        for (int i = prefix.length() - 1; i >= 0; i--)
        {
            node = node->next[prefix[i] - 'a'];
            if (node == NULL)
            {
                return false;
            }
        }
        return true;
    }
};
class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
         for (int i = 0; i < words.size(); i++)
    {
        for (int j = 0; j < words.size() - i - 1; j++)
        {
            if (words[j].length() < words[j + 1].length())
            {
                string t = words[j];
                words[j] = words[j + 1];
                words[j + 1] = t;
            }
        }
    }//冒泡排序
        Trie* root=new Trie();
        int count =0;
        for(int i=0;i<words.size();i++)
        {
            if(root->startsWith(words[i]))//如果能找到
            {
                continue;
            }
            else
            {
                root->insert(words[i]);
                count+=(words[i].length()+1);
            }//如果找不到
        }
        return count;
    }

};