【拓扑排序】火星词典

news/2025/3/18 19:03:44/

文章目录


在这里插入<a class=图片描述" width="300" />

LCR 114. 火星词典

LCR 114. 火星词典

​ 现有一种使用英语字母的外星文语言,这门语言的字母顺序与英语顺序不同。

​ 给定一个字符串列表 words ,作为这门语言的词典,words 中的字符串已经 按这门新语言的字母顺序进行了排序

​ 请你根据该词典还原出此语言中已知的字母顺序,并 按字母递增顺序 排列。若不存在合法字母顺序,返回 "" 。若存在多种可能的合法字母顺序,返回其中 任意一种 顺序即可。

字符串 s 字典顺序小于 字符串 t 有两种情况:

  • 在第一个不同字母处,如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前,那么 s 的字典顺序小于 t
  • 如果前面 min(s.length, t.length) 字母都相同,那么 s.length < t.length 时,s 的字典顺序也小于 t

示例 1:

输入:words = ["wrt","wrf","er","ett","rftt"]
输出:"wertf"

示例 2:

输入:words = ["z","x"]
输出:"zx"

示例 3:

输入:words = ["z","x","z"]
输出:""
解释:不存在合法字母顺序,因此返回 "" 。

提示:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] 仅由小写英文字母组成

注意:本题与主站 269 题相同: https://leetcode-cn.com/problems/alien-dictionary/


解题思路:拓扑排序

​ 这道题的题意其实不太好理解,很容易让人以为 words 中每个字符串也是按照火星词典的字母顺序排序的,但是并没有,words 中每个字符串中出现的字母都是随机的,所以我们只需要关心字符串字符串之间的关系即可!

​ 并且我们最后要得到的是每个字母之间的顺序,其实就相当于是一个有向的指向,所以我们可以根据字符串之间的大小关系,推出每个字母之间的关系,让排序靠前的字母指向排序靠后的字母,最后来一个拓扑排序,得到的就是一个有指向关系的字符串结果!如下所示:

在这里插入<a class=图片描述" width="600" />

​ 拓扑问题对我们来说是小问题,所以现在 问题转变为如何建立这个,让字母之间有次序的指向!

​ 现在的思路就是,我们枚举 words 中的两两字符串进行比较,不过我们保持让 words[i] 表示排在前面的字符串,让 words[j] 表示排在后面的字符串,这样子对比的话我们只需要写一份对比代码即可!

​ 然后比对过程中,我们将 words[i]words[j] 交给 build() 函数去根据题目要求进行建以及入度的计算即可,这里使用的是双指针的思想,但是我们只需要用一个变量 cur 来表示字符串当前的位置即可,因为我们要比对的是字符串中每个对应位置的字母!

​ 比对的步骤如下所示:

  1. 用一个变量 cur 表示 s1s2 的对应字符,然后开始遍历两个字符串
  2. 遍历过程中,只有遇到 s1[cur]s2[cur] 不相等才进行处理
    • 如果相等的话,此时的对比没有意义,因为我们要找到其大小关系。
    • 如果不相等的话,此时因为 s1 是排在 s2 前面的,所以就能得到 s1[cur] 一定是排在 s2[cur] 前面的,也就是说 s1[cur] 指向 s2[cur],所以我们将这个指向添加到邻接表中,然后 s2[cur] 的入度加一即可
    • 因为只需要判断第一次出现不相等的字母,而后面的字母就没有影响了,所以 直接 break
  3. 循环上述操作直到 cur 走完 s1 或者 s2 字符串为止。
  4. 最后需要判断一下是否不符合规则:也就是判断前面字符串的长度是否比后面字符串长度要长,长的话是不行的,因为 "abc""ab" 对比的话根据题目的要求是 "abc" 排在后面的,此时就错了,所以 如果前面字符串的长度比后面字符串长度要长,则该函数返回 false

在这里插入<a class=图片描述" width="600" />

剩下就是处理一些细节问题了:

  1. 因为这道题邻接表存放的是字符,所以我们得用哈希表 unordered_map<char, vector<char>> 来作为邻接表的结构,但是因为考虑到在对比过程中我们需要做去重,而去重的内容就是哈希表中的 vector<char> 部分,此时如果每次都要遍历数组去判断是否存在重复内容的话,就太慢了,所以考虑将数组改为哈希表来存储,最后得到的结构就是 unordered_map<char, unordered_set<char>> 来作为邻接表,还能达到快速索引判重的效果
  2. 因为我们在对比字符串的时候,对于不相等字母处理的时候,如果不存在该指向的话,是需要将其加入到建内容中的,此时还要让被指向的节点的入度减一,因为存放的是字母,所以我们就用 哈希表来存储每个节点的入度,所以最后的结构就是 unordered_map<char, int>
  3. 我们 需要在最开始就初始化入度表,因为后面在建的时候可能那些入度为 0 的节点没被处理到,所以要提前将字符串中出现过的字母都初始化到入度表中,防止后面在拓扑排序的时候,连最开始的循环的进不去!
class Solution {
private:unordered_map<char, unordered_set<char>> edges; // 哈希表嵌套哈希表,是为了快速索引unordered_map<char, int> in_degree;             // 统计入度
public:string alienOrder(vector<string>& words) {// 1. 映射字母:将words中出现的字母初始化到in_degree中,否则后面会出现拿不到入度为0的节点的情况for(int i = 0; i < words.size(); ++i)for(int j = 0; j < words[i].size(); ++j)in_degree[words[i][j]] = 0;// 2. 建,以及入度的计算for(int i = 0; i < words.size() - 1; ++i){for(int j = i + 1; j < words.size(); ++j){bool check = build(words[i], words[j]);// 判断一下是否不符合规则:前面字符串的长度比后面字符串长度要长if(check == true)return "";}}// 3. 将所有入度为0的节点加入到队列中//  (在此之前必须将所有出现的字母都添加到in_degree中并且初始化为0,不然入度为0的节点没被算入)queue<char> bfs;for(auto& e : in_degree){if(e.second == 0)bfs.push(e.first);}// 4. 进行拓扑排序string ret;while(!bfs.empty()){char front = bfs.front();bfs.pop();ret += front; // 添加当前字母到结果集中// 将与front相连的节点的入度减一,如果出现入度为0的节点,则将其加入队列中for(auto& c : edges[front]){in_degree[c]--;if(in_degree[c] == 0)bfs.push(c);}// 最后将当前节点从哈希表中删掉edges.erase(front);}// 5. 判断哈希表是否有没处理的节点,是的话说明存在环,则直接返回空即可return edges.size() == 0 ? ret : "";}bool build(const string& s1, const string& s2){// 使用双指针方法,根据题目要求进行建以及入度的计算int cur = 0;while(cur < s1.size() && cur < s2.size()){// 只有不相等才处理if(s1[cur] != s2[cur]){char a = s1[cur], b = s2[cur]; // 这里是a->b// 如果不存在由a->b的话,则将其加入if(edges[a].count(b) == 0){edges[a].insert(b);in_degree[b]++;}// 因为只需要判断第一对不相等的字符,后面的字符是没有影响的,所以breakbreak; }cur++;}// 判断一下是否不符合规则:前面字符串的长度比后面字符串长度要长if(cur < s1.size() && cur == s2.size())return true;return false;}
};

在这里插入<a class=图片描述" width="300" />


http://www.ppmy.cn/news/1580133.html

相关文章

【CSS】二、浏览器调试与文字样式

文章目录 1、谷歌调试前端代码2、文字属性控制2.1 字体大小2.2 字体粗细2.3 字体倾斜2.4 行高2.5 字体族2.6 复合属性2.7 文本缩进2.8 文本对齐方式2.9 文本修饰线2.10 文字颜色 3、练习 1、谷歌调试前端代码 CommandOptionI或者F12打开开发者模式&#xff0c;选中元素栏Eleme…

Android 数据持久化之 SharedPreferences 存储

1、概述 SharedPreferences 是 Android 提供的一种轻量级存储类&#xff0c;用于存储简单的键值对数据。它非常适合保存应用的配置信息、用户偏好设置等。SharedPreferences支持数据类型String、int、float、long、boolean、Set&#xff08;字符串集合&#xff09;&#xff0c…

Secs/Gem第二讲 (基于secs4net项目的ChatGpt介绍)

好的&#xff0c;我们正式进入&#xff1a; 第二讲&#xff1a;深入 SECS4NET 项目结构——主机程序是怎么搭起来的&#xff1f; 关键词&#xff1a;项目结构、类图、通信类、事件处理、连接生命周期、异步机制 本讲目的 我们从源码入手&#xff0c;一步步搞懂&#xff1a; S…

【品铂科技】在高精度定位行业内的口碑怎么样?

1. ‌技术实力与行业认可‌ 公司自主研发的ABELL无线实时定位系统在复杂环境中&#xff08;如工业、司法监狱等&#xff09;展现出厘米级&#xff08;5-10厘米&#xff09;高精度定位能力&#xff0c;客户反馈系统稳定性强、抗干扰能力突出&#xff0c;成为行业技术标杆‌。参…

Spring Boot中@Valid 与 @Validated 注解的详解

Spring Boot中Valid 与 Validated 注解的详解 引言Valid注解功能介绍使用场景代码样例 Validated注解功能介绍使用场景代码样例 Valid与Validated的区别结论 引言 在Spring Boot应用中&#xff0c;参数校验是确保数据完整性和一致性的重要手段。Valid和Validated注解是Spring …

Spring中Bean的自动装配

1.自动装配的核心概念 定义&#xff1a; Bean的自动装配是Spring框架中用于自动满足Bean依赖的一种机制。通过自动装配&#xff0c;Spring容器会在应用上下文中为某个Bean寻找其依赖的Bean&#xff0c;从而减少手动配置的工作量。其核心目标是减少配置代码&#xff0c;通过类型…

jenkins 配置邮件问题整理

版本&#xff1a;Jenkins 2.492.1 插件&#xff1a; A.jenkins自带的&#xff0c; B.安装功能强大的插件 配置流程&#xff1a; 1. jenkins->系统配置->Jenkins Location 此处的”系统管理员邮件地址“&#xff0c;是配置之后发件人的email。 2.配置系统自带的邮件A…

学习threejs,使用MeshFaceMaterial面材质容器

&#x1f468;‍⚕️ 主页&#xff1a; gis分享者 &#x1f468;‍⚕️ 感谢各位大佬 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍⚕️ 收录于专栏&#xff1a;threejs gis工程师 文章目录 一、&#x1f340;前言1.1 ☘️THREE.MeshFaceMaterial 二…