golang力扣leetcode 剑指Offer II 114. 外星文字典

• 剑指Offer II 114. 外星文字典
• 题解
• 代码

剑指Offer II 114. 外星文字典

题目：这题题目属实写的跟屎一样，样例给的也有问题

现在有一种外星文，与a…z顺序不同，给出一个用外星文构造的字符串列表。

注意：

1. 字符串内部的字符排列，不是根据外星文排序的

2. 字符串与字符串之间，谁排在前面，谁排在后面，是根据外星文排序的

请根据该字符串数组，还原出外星人字典序。如果不存在合法字母顺序，返回”“，答案可能有多个，返回任意一个。

在两个字符串相同下标的字符，称为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 ""
}