LeetCode 269. Alien Dictionary 题解

LeetCode 269. Alien Dictionary 题解题目描述现有一种使用英语字母的外星文语言这门语言的字母顺序与英语顺序不同。给你一个字符串列表words作为这门语言的词典words中的字符串已经按这门新语言的字母顺序进行了排序。请你根据该词典还原出此语言中已知的字母顺序并按字母顺序返回一个字符串。若不存在合法字母顺序返回。示例 1输入words [wrt, wrf, er, ett, rftt] 输出wertf示例 2输入words [z, x] 输出zx示例 3输入words [z, x, z] 输出 解释存在循环依赖z - x - z解题思路使用拓扑排序解决构建字符之间的依赖关系邻接表统计每个字符的入度使用队列进行拓扑排序代码实现from collections import defaultdict, deque def alienOrder(words): # 构建邻接表和入度 adj defaultdict(set) in_degree {} # 初始化所有字符的入度为 0 for word in words: for c in word: in_degree[c] 0 # 构建邻接表和计算入度 for i in range(len(words) - 1): word1, word2 words[i], words[i1] # 检查是否是前缀关系 if len(word1) len(word2) and word1.startswith(word2): return # 找到第一个不同的字符 for j in range(min(len(word1), len(word2))): c1, c2 word1[j], word2[j] if c1 ! c2: if c2 not in adj[c1]: adj[c1].add(c2) in_degree[c2] 1 break # 拓扑排序 queue deque() for c in in_degree: if in_degree[c] 0: queue.append(c) result [] while queue: c queue.popleft() result.append(c) for neighbor in adj[c]: in_degree[neighbor] - 1 if in_degree[neighbor] 0: queue.append(neighbor) # 检查是否所有字符都被处理 if len(result) ! len(in_degree): return return .join(result)复杂度分析时间复杂度O(C)其中 C 是所有单词的总字符数空间复杂度O(1)因为字母数量有限测试案例# 测试案例 1 assert alienOrder([wrt, wrf, er, ett, rftt]) wertf # 测试案例 2 assert alienOrder([z, x]) zx # 测试案例 3 assert alienOrder([z, x, z]) # 测试案例 4 assert alienOrder([ab, abc]) abc总结本题是拓扑排序的经典应用。关键点构建字符之间的依赖关系处理前缀情况拓扑排序检测环通过本题可以深入理解拓扑排序在实际问题中的应用。