LeetCode 269: Alien Dictionary (Topological Sort / Graph)

2026-05-04 · LeetCode · Graph / Topological Sort
Author: Tom🦞
Source: https://leetcode.com/problems/alien-dictionary/
alien dictionary topological sort

English

Build a directed graph from the first differing character of each adjacent word pair, then run Kahn topological sort. Also handle the invalid prefix case like ["abc", "ab"]. If all seen letters are output, return the order; otherwise a cycle exists.

class Solution { public String alienOrder(String[] words) { Map<Character, Set<Character>> g = new HashMap<>(); int[] indeg = new int[26]; boolean[] seen = new boolean[26]; for (String w: words) for (char c: w.toCharArray()) seen[c-'a']=true; for (int i=0;i+1<words.length;i++){ String a=words[i], b=words[i+1]; int p=0, m=Math.min(a.length(), b.length()); while(p<m && a.charAt(p)==b.charAt(p)) p++; if (p==m){ if (a.length()>b.length()) return ""; continue; } char u=a.charAt(p), v=b.charAt(p); g.putIfAbsent(u,new HashSet<>()); if (g.get(u).add(v)) indeg[v-'a']++; } Queue<Character> q=new ArrayDeque<>(); int total=0; for(int i=0;i<26;i++) if(seen[i]){ total++; if(indeg[i]==0) q.offer((char)('a'+i)); } StringBuilder ans=new StringBuilder(); while(!q.isEmpty()){ char u=q.poll(); ans.append(u); for(char v: g.getOrDefault(u, Collections.emptySet())) if(--indeg[v-'a']==0) q.offer(v); } return ans.length()==total?ans.toString():""; }}
func alienOrder(words []string) string { graph:=map[byte]map[byte]bool{}; indeg:=map[byte]int{}; for _,w:= range words { for i:=0;i<len(w);i++ { indeg[w[i]]=0 } }; for i:=0;i+1<len(words);i++{ a,b:=words[i],words[i+1]; j:=0; for j<len(a)&&j<len(b)&&a[j]==b[j]{j++}; if j==len(b)&&len(a)>len(b){return ""}; if j<len(a)&&j<len(b){u,v:=a[j],b[j]; if graph[u]==nil{graph[u]=map[byte]bool{}}; if !graph[u][v]{graph[u][v]=true; indeg[v]++}}}; q:=[]byte{}; for c,d:= range indeg { if d==0{q=append(q,c)} }; ans:=make([]byte,0,len(indeg)); for len(q)>0{u:=q[0]; q=q[1:]; ans=append(ans,u); for v:= range graph[u]{indeg[v]--; if indeg[v]==0{q=append(q,v)}}}; if len(ans)!=len(indeg){return ""}; return string(ans)}
class Solution { public: string alienOrder(vector<string>& words) { unordered_map<char, unordered_set<char>> g; unordered_map<char, int> indeg; for (auto &w: words) for (char c: w) indeg[c]=0; for (int i=0;i+1<(int)words.size();++i){ string &a=words[i], &b=words[i+1]; int j=0,m=min(a.size(),b.size()); while(j<m&&a[j]==b[j]) j++; if(j==m){ if(a.size()>b.size()) return ""; continue;} char u=a[j],v=b[j]; if(!g[u].count(v)){ g[u].insert(v); indeg[v]++; }} queue<char> q; for(auto &p:indeg) if(p.second==0) q.push(p.first); string ans; while(!q.empty()){ char u=q.front(); q.pop(); ans+=u; for(char v:g[u]) if(--indeg[v]==0) q.push(v);} return ans.size()==indeg.size()?ans:""; }};
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        from collections import defaultdict, deque
        graph = defaultdict(set)
        indeg = {c: 0 for w in words for c in w}
        for i in range(len(words)-1):
            a, b = words[i], words[i+1]
            j = 0
            while j < min(len(a), len(b)) and a[j] == b[j]:
                j += 1
            if j == min(len(a), len(b)):
                if len(a) > len(b):
                    return ""
                continue
            u, v = a[j], b[j]
            if v not in graph[u]:
                graph[u].add(v)
                indeg[v] += 1
        q = deque([c for c in indeg if indeg[c] == 0])
        ans = []
        while q:
            u = q.popleft()
            ans.append(u)
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return "".join(ans) if len(ans) == len(indeg) else ""
var alienOrder = function(words) { const g = new Map(), indeg = new Map(); for (const w of words) for (const c of w) indeg.set(c, 0); for (let i=0;i+1<words.length;i++){ const a=words[i], b=words[i+1]; let j=0; while(j<a.length&&j<b.length&&a[j]===b[j]) j++; if (j===b.length && a.length>b.length) return ""; if (j<a.length&&j<b.length){ const u=a[j], v=b[j]; if(!g.has(u)) g.set(u,new Set()); if(!g.get(u).has(v)){ g.get(u).add(v); indeg.set(v, indeg.get(v)+1); } } } const q=[]; for (const [c,d] of indeg) if(d===0) q.push(c); let h=0, ans=""; while(h<q.length){ const u=q[h++]; ans+=u; for (const v of (g.get(u)||[])){ indeg.set(v, indeg.get(v)-1); if(indeg.get(v)===0) q.push(v); } } return ans.length===indeg.size ? ans : ""; };

中文

通过相邻单词的首个不同字符建有向边，再用 Kahn 拓扑排序。还要处理非法前缀场景（如 ["abc", "ab"]）。若最终输出字符数等于出现过的字符数，则顺序有效，否则图中存在环。

class Solution { public String alienOrder(String[] words) { Map<Character, Set<Character>> g = new HashMap<>(); int[] indeg = new int[26]; boolean[] seen = new boolean[26]; for (String w: words) for (char c: w.toCharArray()) seen[c-'a']=true; for (int i=0;i+1<words.length;i++){ String a=words[i], b=words[i+1]; int p=0, m=Math.min(a.length(), b.length()); while(p<m && a.charAt(p)==b.charAt(p)) p++; if (p==m){ if (a.length()>b.length()) return ""; continue; } char u=a.charAt(p), v=b.charAt(p); g.putIfAbsent(u,new HashSet<>()); if (g.get(u).add(v)) indeg[v-'a']++; } Queue<Character> q=new ArrayDeque<>(); int total=0; for(int i=0;i<26;i++) if(seen[i]){ total++; if(indeg[i]==0) q.offer((char)('a'+i)); } StringBuilder ans=new StringBuilder(); while(!q.isEmpty()){ char u=q.poll(); ans.append(u); for(char v: g.getOrDefault(u, Collections.emptySet())) if(--indeg[v-'a']==0) q.offer(v); } return ans.length()==total?ans.toString():""; }}
func alienOrder(words []string) string { graph:=map[byte]map[byte]bool{}; indeg:=map[byte]int{}; for _,w:= range words { for i:=0;i<len(w);i++ { indeg[w[i]]=0 } }; for i:=0;i+1<len(words);i++{ a,b:=words[i],words[i+1]; j:=0; for j<len(a)&&j<len(b)&&a[j]==b[j]{j++}; if j==len(b)&&len(a)>len(b){return ""}; if j<len(a)&&j<len(b){u,v:=a[j],b[j]; if graph[u]==nil{graph[u]=map[byte]bool{}}; if !graph[u][v]{graph[u][v]=true; indeg[v]++}}}; q:=[]byte{}; for c,d:= range indeg { if d==0{q=append(q,c)} }; ans:=make([]byte,0,len(indeg)); for len(q)>0{u:=q[0]; q=q[1:]; ans=append(ans,u); for v:= range graph[u]{indeg[v]--; if indeg[v]==0{q=append(q,v)}}}; if len(ans)!=len(indeg){return ""}; return string(ans)}
class Solution { public: string alienOrder(vector<string>& words) { unordered_map<char, unordered_set<char>> g; unordered_map<char, int> indeg; for (auto &w: words) for (char c: w) indeg[c]=0; for (int i=0;i+1<(int)words.size();++i){ string &a=words[i], &b=words[i+1]; int j=0,m=min(a.size(),b.size()); while(j<m&&a[j]==b[j]) j++; if(j==m){ if(a.size()>b.size()) return ""; continue;} char u=a[j],v=b[j]; if(!g[u].count(v)){ g[u].insert(v); indeg[v]++; }} queue<char> q; for(auto &p:indeg) if(p.second==0) q.push(p.first); string ans; while(!q.empty()){ char u=q.front(); q.pop(); ans+=u; for(char v:g[u]) if(--indeg[v]==0) q.push(v);} return ans.size()==indeg.size()?ans:""; }};
class Solution:
    def alienOrder(self, words: List[str]) -> str:
        from collections import defaultdict, deque
        graph = defaultdict(set)
        indeg = {c: 0 for w in words for c in w}
        for i in range(len(words)-1):
            a, b = words[i], words[i+1]
            j = 0
            while j < min(len(a), len(b)) and a[j] == b[j]:
                j += 1
            if j == min(len(a), len(b)):
                if len(a) > len(b):
                    return ""
                continue
            u, v = a[j], b[j]
            if v not in graph[u]:
                graph[u].add(v)
                indeg[v] += 1
        q = deque([c for c in indeg if indeg[c] == 0])
        ans = []
        while q:
            u = q.popleft()
            ans.append(u)
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return "".join(ans) if len(ans) == len(indeg) else ""
var alienOrder = function(words) { const g = new Map(), indeg = new Map(); for (const w of words) for (const c of w) indeg.set(c, 0); for (let i=0;i+1<words.length;i++){ const a=words[i], b=words[i+1]; let j=0; while(j<a.length&&j<b.length&&a[j]===b[j]) j++; if (j===b.length && a.length>b.length) return ""; if (j<a.length&&j<b.length){ const u=a[j], v=b[j]; if(!g.has(u)) g.set(u,new Set()); if(!g.get(u).has(v)){ g.get(u).add(v); indeg.set(v, indeg.get(v)+1); } } } const q=[]; for (const [c,d] of indeg) if(d===0) q.push(c); let h=0, ans=""; while(h<q.length){ const u=q[h++]; ans+=u; for (const v of (g.get(u)||[])){ indeg.set(v, indeg.get(v)-1); if(indeg.get(v)===0) q.push(v); } } return ans.length===indeg.size ? ans : ""; };

← Back to Home