剑指Offer II 114. 外星文字典
剑指Offer II 114. 外星文字典
题解
题目：这题题目属实写的跟屎一样，样例给的也有问题
现在有一种外星文，与a…z顺序不同，给出一个用外星文构造的字符串列表。
注意：
- 字符串内部的字符排列，不是根据外星文排序的
- 字符串与字符串之间，谁排在前面，谁排在后面，是根据外星文排序的
请根据该字符串数组，还原出外星人字典序。如果不存在合法字母顺序，返回”“，答案可能有多个，返回任意一个。
在两个字符串相同下标的字符，称为ch1和ch2,在第二种情况中，排在前面的字符串，必定ch1 < ch2 。如果字符相同，len(word1) < len(word2) 。
思路：
其实很容易想到拓扑排序，恶心的是题目描述，重点在于注意那里 1. 既然字符串内部的字符串排列顺序是未知的 2. 那么只能通过相同字符串来建边 3. abc,ab这种样例是不应该出现的，但是样例里面有，题目说给定的是按照排序后的数组,那只能算这种是不合法的了。 4. 对于这种情况，就判断len(word1) > len(word2) 5. 一旦在相同下标有不相等的字符，就立马建边，break，由于现在下标字符的优先级，后面的字符是不可靠的了 6. 建边之后拓扑排序即可
代码
func alienOrder(words []string) string { inDeg := make(map[byte]int) graph := make(map[byte][]byte) for _, word := range words { for _, ch := range word { inDeg[byte(ch)] = 0 //统计外星文一共有多少字符 } } for i := 0; i < len(words)-1; i++ { word1 := words[i] word2 := words[i+1] flag := false for j := 0; ; j++ { ch1 := word1[j] ch2 := word2[j] if ch1 != ch2 { //判断两个单词的字符是否一样 graph[ch1] = append(graph[ch1], ch2) //不同则建边 inDeg[ch2]++ //入度加一 break } if j == len(word1)-1 || j == len(word2)-1 { //如果flag为true说明字符都相同 flag = true break } } if flag && len(word1) > len(word2) { //abc ab的情况，不合法 return "" } } ans := make([]byte, 0) for k, v := range inDeg { if v == 0 { //对于入度为0的字符来说，我们无法确定其顺序，直接加入即可 ans = append(ans, k) } } queue := make([]byte, len(ans)) copy(queue, ans) for len(queue) > 0 { //拓扑排序 u := queue[0] queue = queue[1:] for _, v := range graph[u] { inDeg[v]-- if inDeg[v] == 0 { ans = append(ans, v) queue = append(queue, v) } } } if len(ans) == len(inDeg) { //如果存在环，那么ans必定缺少字符 return string(ans) } return "" }
