标签搜索

目 录CONTENT

文章目录

美团--最小唯一前缀.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 7 阅读 / 1,417 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

美团--最小唯一前缀

@[toc]

一、问题描述

给定一组个字符串为每个字符串找出能够唯一识别该字符串的最小前缀

  •  输入描述:
第一行输入一个整数 n 表示字符串个数
后面n行,每行一个字符串,一共n串互不相同的字符串。(2 <= n <= 100,
字符串长度不超过100)
  •  输出描述:
输出n行,每行一个字符串,依次是每个字符串的最小可唯一识别前缀

输入例子1:
5
meituanapp
meituanwaimai
dianpingliren
dianpingjiehun
mt

输出例子1:
meituana
meituanw
dianpingl
dianpingj
mt

二、分析

  •  这个是经典的字典树的题目,Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。
  •  实现原理:

利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。

三、代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

//Trie树节点结构
struct Node
{
    int cnt;//用来标记该字符所在节点的访问次数
    Node* next[26];  //指向26个小写的字母 a-z的节点指针
 
 	// 对于最优前缀树的每个节点都要将指针数组初始化为nullptr, 
 	// 每一个cnt都要初始化为1
    Node()  
       :cnt(1)
    {
        for (int i = 0; i < 26; i++)
        {
            next[i] = nullptr;
        }
    }
};
 
int main()
{
    Node*root = new Node();
    int n = 0;
    cin >> n;
    vector<string> strs(n);
    for (int i = 0; i < n; i++)
    {
        string tmp;
        cin >> tmp; //对于每一个输入的字符串,就构造前缀树,加入七十中
        strs[i] = tmp;
        Node* p = root;
        for (int j = 0; j < tmp.size(); j++)
        {
            if (p->next[tmp[j] - 'a'] != nullptr) // 节点的下一个 next[tmp[j] - 'a']不为空
            {
                p->next[tmp[j] - 'a']->cnt++; // 对这个节点的标记值 cnt++
            }
            else
            {
                p->next[tmp[j] - 'a'] = new Node();  //创建新的节点
            }
            p = p->next[tmp[j] - 'a']; // 将指针指向 下一个节点
        }
    }
    for (int i = 0; i < n; i++)
    {
        Node* p = root;
        int j = 0;
        for (; j < strs[i].size(); j++)
        {
            if (p->next[strs[i][j] - 'a']->cnt == 1)
            {
                cout << strs[i].substr(0, j + 1) << endl;  // 输处从头结点到 cnt=1位置的整个字符
                break;
            }
            p = p->next[strs[i][j] - 'a'];
        }
        if (j == strs[i].size())  // 代表整个字符串才是唯一可区分的
        {
            cout << strs[i] << endl;
        }
    }
    return 0;
}

0

评论区