class Solution {
public:
string alienOrder(vector<string>& words) {
}
};
剑指 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 <= 1001 <= words[i].length <= 100words[i] 仅由小写英文字母组成
注意：本题与主站 269 题相同： https://leetcode.cn/problems/alien-dictionary/
原站题解
java 解法, 执行用时: 3 ms, 内存消耗: 39.7 MB, 提交时间: 2023-04-22 12:33:44
class Solution {
public String alienOrder(String[] words) {
Map<Character, List<Character>> graph = new HashMap<>();
Set<Character> set = new HashSet<>();
int[] d = new int[26];
out:
for(int i = 0; i < words.length; i++) {
for(int j = 0; j < words[i].length(); j++) {
set.add(words[i].charAt(j));
}
if(i < words.length - 1) {
for(int j = 0; j < Math.min(words[i].length(), words[i + 1].length()); j++) {
char c1 = words[i].charAt(j), c2 = words[i + 1].charAt(j);
if(c1 != c2) {
List<Character> nxt = graph.getOrDefault(c1, new ArrayList<>());
nxt.add(c2);
graph.put(c1, nxt);
d[c2 - 'a']++;
continue out;
}
}
if(words[i].length() > words[i + 1].length()) {
return "";
}
}
}
StringBuilder sb = new StringBuilder();
for(char c: set) {
if(d[c - 'a'] == 0) {
sb.append(c);
}
}
for(int i = 0;i < sb.length(); i++) {
char c = sb.charAt(i);
if(graph.containsKey(c)) {
for(char nxt: graph.get(c)) {
if(--d[nxt - 'a'] == 0) {
sb.append(nxt);
}
}
}
}
return sb.length() == set.size() ? sb.toString() : "";
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-04-22 12:33:27
func alienOrder(words []string) string {
graph, set, d := map[byte][]byte{}, map[byte]bool{}, make([]int, 26)
out:
for i, word := range words {
for j := range word {
set[word[j]] = true
}
if i < len(words) - 1 {
for j := 0; j < min(len(words[i]), len(words[i + 1])); j++ {
if words[i][j] != words[i + 1][j] {
graph[words[i][j]] = append(graph[words[i][j]], words[i + 1][j])
d[words[i + 1][j] - 'a']++
continue out
}
}
if len(words[i]) > len(words[i + 1]) {
return ""
}
}
}
ans := []byte{}
for s := range set {
if d[s - 'a'] == 0 {
ans = append(ans, s)
}
}
for i := 0; i < len(ans); i++ {
for _, nxt := range graph[ans[i]] {
d[nxt - 'a']--
if d[nxt - 'a'] == 0 {
ans = append(ans, nxt)
}
}
}
if len(ans) == len(set) {
return string(ans)
}
return ""
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2023-04-22 12:32:42
class Solution:
def alienOrder(self, words: List[str]) -> str:
graph, s = defaultdict(list), set()
for w in words:
s = s.union(set(w))
d = [0] * 26
for a, b in pairwise(words):
for ca, cb in zip(a, b):
if ca != cb:
graph[ca].append(cb)
d[ord(cb) - ord('a')] += 1
break
else:
if len(a) > len(b):
return ""
start = [k for k in s if d[ord(k) - ord('a')] == 0]
for ch in start:
for nxt in graph[ch]:
d[v := ord(nxt) - ord('a')] -= 1
if not d[v]:
start.append(nxt)
return "".join(start) if len(start) == len(s) else ""
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2023-04-22 12:32:11
from graphlib import TopologicalSorter
class Solution:
def alienOrder(self, words: List[str]) -> str:
n = len(words)
ts = TopologicalSorter()
seen = set(words[-1])
for i in range(n - 1):
if len(words[i]) > len(words[i + 1]) and words[i].startswith(words[i + 1]):
return ''
seen.update(words[i])
for c1, c2 in zip(words[i], words[i + 1]):
if c1 == c2: continue
ts.add(c2, c1)
break
for ch in seen:
ts.add(ch)
try:
return ''.join(ts.static_order())
except:
return ''