LeetCode 269 Alien Dictionary

LeetCode

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language’s dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Example 1:

Input: words = [“wrt”,”wrf”,”er”,”ett”,”rftt”]
Output: “wertf”

Example 2:

Input: words = [“z”,”x”]
Output: “zx”

Example 3:

Input: words = [“z”,”x”,”z”]
Output: “”
Explanation: The order is invalid, so return "".

Constraints:

1 <= words.length <= 100 1 <= words[i].length <= 100
* words[i] consists of only lowercase English letters.

算法思路：

N/A

注意事项：

1. 题目要求： 空字符顺序前于非空字母，否则字典不合法，如abc -> ab, c不能前于空字符，无解。简而言之，后面单词不能是前面的前缀return False if len(word) > len(word2) else True
2. 模板问题： graph要含所有节点，包括没有边的节点。否则结果会有遗漏graph = Counter({c: [] for word in words for c in word})
3. 模板问题： in_degree初始化要对所有节点赋0， in_degree[c] = 0。in_degree = collections.defaultdict(int)并不能产生key
4. 模板问题： 第四步判断是否含循环必不可少，题目要求可能不合法，return res if len(graph) == len(res) else ‘’
5. 语法错误： graph.items()记得加items。res是str不是list

Python代码：

def alienOrder(self, words: List[str]) -> str:
	# graph = collections.defaultdict(list)
	graph = Counter({c: [] for word in words for c in word})
	for i in range(1, len(words)):
		if not self.populate_one_order(words[i - 1], words[i], graph):
			return ''
	in_degree = collections.defaultdict(int)
	for c in graph.keys():
		in_degree[c] = 0
	for key, li in graph.items():
		for j in range(len(li)):
			in_degree[li[j]] += 1
	res = ''
	queue = deque([node for node, in_degree_num in in_degree.items() if in_degree_num == 0])
	while queue:
		node = queue.popleft()
		res += node
		for neighbor in graph[node]:
			in_degree[neighbor] -= 1
			if in_degree[neighbor] == 0:
				queue.append(neighbor)
	return res if len(graph) == len(res) else ''

def populate_one_order(self, word, word2, graph):
	for j in range(min(len(word), len(word2))):
		if word[j] != word2[j]:
			graph[word[j]].append(word2[j])
			return True
	return False if len(word) > len(word2) else True

算法分析：

时间复杂度为O(V + E)，空间复杂度O(O + E)，V为节点数，E为边数，n为单词数，L为最长单词长度，O = nL， E = L，而空间复杂度图的空间为O + E，而queue空间最多为26条边，26个字母，in_degree空间为O(V)。所以总的时间复杂度为O(nL)，空间复杂度O(nL)