## Alien Dictionary

• Time:O(26 + |\texttt{words}| - 1)
• Space:O(26 + |\texttt{words}| - 1)

## C++

``````class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> graph;
vector<int> inDegree(26);
buildGraph(graph, words, inDegree);
}

private:
void buildGraph(unordered_map<char, unordered_set<char>>& graph,
const vector<string>& words, vector<int>& inDegree) {
// create node for each character in each word
for (const string& word : words)
for (const char c : word)
if (!graph.count(c))
graph[c] = unordered_set<char>();

for (int i = 1; i < words.size(); ++i) {
const string& first = words[i - 1];
const string& second = words[i];
const int length = min(first.length(), second.length());
for (int j = 0; j < length; ++j) {
const char u = first[j];
const char v = second[j];
if (u != v) {
if (!graph[u].count(v)) {
graph[u].insert(v);
++inDegree[v - 'a'];
}
break;  // later characters' order are meaningless
}
// first = "ab", second = "a" -> invalid
if (j == length - 1 && first.length() > second.length()) {
graph.clear();
return;
}
}
}
}

string topology(unordered_map<char, unordered_set<char>>& graph,
vector<int>& inDegree) {
string s;
queue<char> q;

for (const auto& [c, _] : graph)
if (inDegree[c - 'a'] == 0)
q.push(c);

while (!q.empty()) {
const char u = q.front();
q.pop();
s += u;
for (const char v : graph[u])
if (--inDegree[v - 'a'] == 0)
q.push(v);
}

// words = ["z", "x", "y", "x"]
return s.length() == graph.size() ? s : "";
}
};
``````

## JAVA

``````class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
int[] inDegree = new int[26];
buildGraph(graph, words, inDegree);
}

private void buildGraph(Map<Character, Set<Character>> graph, String[] words, int[] inDegree) {
// create node for each character in each word
for (final String word : words)
for (final char c : word.toCharArray())
graph.putIfAbsent(c, new HashSet<>());

for (int i = 1; i < words.length; ++i) {
final String first = words[i - 1];
final String second = words[i];
final int length = Math.min(first.length(), second.length());
for (int j = 0; j < length; ++j) {
final char u = first.charAt(j);
final char v = second.charAt(j);
if (u != v) {
if (!graph.get(u).contains(v)) {
++inDegree[v - 'a'];
}
break; // later characters' order are meaningless
}
// first = "ab", second = "a" -> invalid
if (j == length - 1 && first.length() > second.length()) {
graph.clear();
return;
}
}
}
}

private String topology(Map<Character, Set<Character>> graph, int[] inDegree) {
StringBuilder sb = new StringBuilder();
Queue<Character> q = graph.keySet()
.stream()
.filter(c -> inDegree[c - 'a'] == 0)
.collect(Collectors.toCollection(ArrayDeque::new));

while (!q.isEmpty()) {
final char u = q.poll();
sb.append(u);
for (final char v : graph.get(u))
if (--inDegree[v - 'a'] == 0)
q.offer(v);
}

// words = ["z", "x", "y", "x"]
return sb.length() == graph.size() ? sb.toString() : "";
}
}
``````

## Python

``````class Solution:
def alienOrder(self, words: List[str]) -> str:
graph = {}
inDegree = [0] * 26

self._buildGraph(graph, words, inDegree)
return self._topology(graph, inDegree)

def _buildGraph(self, graph: Dict[chr, Set[chr]], words: List[str], inDegree: List[int]) -> None:
# create node for each character in each word
for word in words:
for c in word:
if c not in graph:
graph[c] = set()

for first, second in zip(words, words[1:]):
length = min(len(first), len(second))
for j in range(length):
u = first[j]
v = second[j]
if u != v:
if v not in graph[u]:
inDegree[ord(v) - ord('a')] += 1
break  # later characters' order are meaningless
# first = 'ab', second = 'a' . invalid
if j == length - 1 and len(first) > len(second):
graph.clear()
return

def _topology(self, graph: Dict[chr, Set[chr]], inDegree: List[int]) -> str:
s = ''
q = deque()

for c in graph:
if inDegree[ord(c) - ord('a')] == 0:
q.append(c)

while q:
u = q.pop()
s += u
for v in graph[u]:
inDegree[ord(v) - ord('a')] -= 1
if inDegree[ord(v) - ord('a')] == 0:
q.append(v)

# words = ['z', 'x', 'y', 'x']
return s if len(s) == len(graph) else ''
``````