剑指 Offer II 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/problems/alien-dictionary/
解法
方法一:拓扑排序 + BFS
用数组 $g$ 记录在火星字典中的字母先后关系,$g[i][j] = true$ 表示字母 $i + 'a'$ 在字母 $j + 'a'$ 的前面;用数组 $s$ 记录当前字典出现过的字母,$cnt$ 表示出现过的字母数。
一个很简单的想法是遍历每一个单词,比较该单词和其后的所有单词,把所有的先后关系更新进数组 $g$,这样遍历时间复杂度为 $O(n^3)$;但是我们发现其实比较相邻的两个单词就可以了,比如 $a < b < c$ 则比较 $a < b$ 和 $b < c$, $a$ 和 $c$ 的关系便确定了。因此算法可以优化成比较相邻两个单词,时间复杂度为 $O(n^2)$。
出现矛盾的情况:
- $g[i][j]$ = $g[j][i]$ = $true$;
- 后一个单词是前一个单词的前缀;
- 在拓扑排序后 $ans$ 的长度小于统计到的字母个数。
拓扑排序:
- 统计所有出现的字母入度;
- 将所有入度为 $0$ 的字母加入队列;
- 当队列不空,出队并更新其他字母的入度,入度为 $0$ 则入队,同时出队时将当前字母加入 $ans$ 的结尾;
- 得到的便是字母的拓扑序,也就是火星字典的字母顺序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
|