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

BFS解决拓扑排序(3)_火星词典

article 2024/11/1 5:42:09

个人主页：C++忠实粉丝
欢迎点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝原创

BFS解决拓扑排序(3)_火星词典

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌

1. 题目链接

2. 题目描述

3. 解法

算法思路:

代码展示:

4, 算法总结

1. 题目链接

OJ链接 : 火星词典

2. 题目描述

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

给定一个字符串列表 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] 仅由小写英文字母组成

3. 解法

算法思路:

将题意搞清楚之后, 这道题就变成了判断有向图时候有无环, 可以用拓扑排序解决.

如何搜集信息 (如何建图):

1. 两层for循环枚举出所有的两个字符串的组合;

2. 然后利用指针, 根据字典序规则找出信息

1. 建图：
使用邻接表 edges 来存储字母间的依赖关系，in 哈希表用来记录每个字母的入度。
首先遍历所有单词，初始化 in 表，确保每个字母都有一个初始值（入度为0）。

2. 确定字母顺序：
使用双重循环比较相邻的单词 words[i] 和 words[j]，调用 add 函数来建立字母之间的顺序关系。
在 add 函数中：
找到第一个不同的字符，设定依赖关系（如 a->b 表示字母 a 在字母 b 之前）。
更新入度，并检查是否有非法情况（如一个单词是另一个单词的前缀而更长）。

3. 拓扑排序：
初始化一个队列，将所有入度为0的字母加入队列。
持续进行 BFS：
从队列中取出一个字母，添加到结果字符串 ret 中。
对于该字母的所有后续字母，减少它们的入度。如果某个字母的入度减为0，则将其加入队列。

4. 验证结果：
最后检查所有字母的入度，如果有字母的入度不为0，说明存在循环依赖关系，返回空字符串；否则，返回结果字符串。

代码展示:

class Solution {
    unordered_map<char, unordered_set<char>> edges;//邻接表来存储图
    unordered_map<char, int> in;//统计入度
    bool cheak;//处理遍历情况
public:
    string alienOrder(vector<string>& words) {
        //1. 建图 + 初始化入度哈希表
        for(auto s : words)
        {
            for(auto ch : s)
            {
                in[ch] = 0;
            }
        }
        int n = words.size();
        for(int i = 0; i < n; i++)
        {
            for(int j = i + 1; j < n; j++)
            {
                add(words[i], words[j]);
                if(cheak) return "";
            }
        }
        queue<char> q;
        string ret;
        for(auto [a, b] : in)
            if(b == 0) q.push(a);
        while(q.size())
        {
            char ch = q.front();
            q.pop();
            ret += ch;
            for(char c : edges[ch])
            {
                in[c]--;
                if(in[c] == 0) q.push(c);
            }
        }
        //判断
        for(auto [a, b] : in)
            if(b != 0) return "";
        return ret;
    }
    void add(string& s1, string& s2)
    {
        int n = min(s1.size(), s2.size());
        int i = 0;
        for(; i < n; i++)
        {
            if(s1[i] != s2[i])
            {
                char a = s1[i], b = s2[i]; //a -> b
                if(!edges.count(a) || !edges[a].count(b))
                {
                    edges[a].insert(b);
                    in[b]++;
                }
                break;
            }
        }
        if(i == s2.size() && i < s1.size()) cheak = true;
    }
};