# Question

Formatted question description: https://leetcode.ca/all/269.html

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.

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.

# Algorithm

This problem is a variant of the classical topological sorting problem, where you’re given a partial order of elements and asked to extend it to a total order.

### Overview

• Graph Representation: The problem is modeled as a directed graph where each node represents a character, and an edge from node u to node v implies that u comes before v in the alien language. The goal is to find a topological ordering of the graph’s nodes, which represents the alphabet of the alien language.

### _buildGraph Method

• Node Initialization: Initializes inDegree for all characters in all words to 0 and prepares the graph. inDegree counts the number of edges pointing to a node, which is used to identify nodes with no incoming edges.

• Graph Construction: By comparing adjacent words in the list, it determines the order between different characters and constructs the graph accordingly. When the first non-matching characters between two words are found, an edge is added from the character in the first word to the character in the second word. This is because the sorted list of words implies that characters in earlier words precede those in later words.

• Edge Addition and inDegree Update: If character v is not already in the adjacency list of u (graph[u]), it adds v to u’s list and increments v’s inDegree. This maintains the count of how many characters come before v.

• Invalid Order Detection: If a longer word comes before a shorter word and they match up to the length of the shorter word, the order is invalid (e.g., “ab” before “a”), and the graph is cleared to signal an invalid configuration.

### _topology Method

• Topological Sort: Implements topological sorting using Kahn’s algorithm. It starts with characters that have an inDegree of 0 (i.e., characters that don’t have any characters preceding them) and adds them to a queue. While the queue is not empty, it removes a character from the queue, appends it to the result string (since this character has no preceding characters or all of them have already been added to the result), and decreases the inDegree of its adjacent characters. If any adjacent character’s inDegree becomes 0, it’s added to the queue.

• Cycle Detection: If, after processing all characters, there are still characters with non-zero inDegree, it means there’s a cycle in the graph, and no valid ordering exists. This scenario returns an empty string.

• Result Validation: Finally, it checks if the length of the result string matches the number of unique characters in inDegree. If not, it means not all characters were accounted for, possibly due to an invalid input, and it returns an empty string if such a case is detected.

### Conclusion

This solution effectively builds a graph to represent the partial ordering of characters inferred from the input list of words, then performs a topological sort on this graph to determine the characters’ order in the alien language. The topological sort also incorporates checks for cycles and invalid configurations, which would indicate that no valid ordering exists.

# Code

• import java.util.*;

public class Alien_Dictionary {

public static void main(String[] args) {
Alien_Dictionary out = new Alien_Dictionary();
Solution s = out.new Solution();
Solution_bfs s2 = out.new Solution_bfs();

String[] words = new String[] {
"wrt",
"wrf",
"er",
"ett",
"rftt"
};

System.out.println(s.alienOrder(words));
System.out.println(s2.alienOrder(words));
}

// ref: http://buttercola.blogspot.com/2015/09/leetcode-alien-dictionary.html
public class Solution_bfs {
/**
* @param words: a list of words
* @return: a string which is correct order
*/
public String alienOrder(String[] words) {
if (words == null || words.length == 0) {
return "";
}

// step 1: construct the graph
//
Map<Character, List<Character>> adjMap = new HashMap<>();

StringBuilder result = new StringBuilder();

// toplogical sorting
//
Map<Character, Integer> indegreeMap = new HashMap<>();
for (Character node : adjMap.keySet()) {
indegreeMap.put(node, 0);
}

for (Character node : adjMap.keySet()) {
for (Character neighbor : adjMap.get(node)) {
int indegree = indegreeMap.get(neighbor);
indegree += 1;
indegreeMap.put(neighbor, indegree);
}
}

// start from indegree=0
Queue<Character> queue = new PriorityQueue<>();
for (Character node : indegreeMap.keySet()) {
if (indegreeMap.get(node) == 0) {
// starting node, can only be one, cannot be 2 starting with 0 indegree
queue.offer(node);
}
}

while (!queue.isEmpty()) {
char curNode = queue.poll();
result.append(curNode);

for (char neighbor : adjMap.get(curNode)) {
int indegree = indegreeMap.get(neighbor);
indegree -= 1;
indegreeMap.put(neighbor, indegree);

// @note: key is here.
// for A->B, B->C, A-C: C will not be counted until its indgree is 0

if (indegree == 0) {
queue.offer(neighbor);
}
}
}

if (result.length() < numNodes) {
return "";
}

return result.toString();
}

private void constructGraph(String[] words, Map<Character, List<Character>> adjMap) {
// construct nodes
for (String word : words) {
for (Character c : word.toCharArray()) {
adjMap.put(c, new ArrayList<>()); // c to all its next
}
}

// construct edges
for (int i = 1; i < words.length; i++) {
String prev = words[i - 1];
String curr = words[i];

for (int j = 0; j < prev.length() && j < curr.length(); j++) {
if (prev.charAt(j) != curr.charAt(j)) {
break;
}
}
}
}
}

public class Solution {
// dfs
public String alienOrder(String[] words) {

// Step 1: build the graph
Map<Character, Set<Character>> graph = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String currentWord = words[i];
for (int j = 0; j < currentWord.length(); j++) {
if (!graph.containsKey(currentWord.charAt(j))) {
graph.put(currentWord.charAt(j), new HashSet<>());
}
}

if (i > 0) {
connectGraph(graph, words[i - 1], currentWord);
}
}

// Step 2: topological sorting
StringBuffer sb = new StringBuffer();
Map<Character, Integer> visited = new HashMap<Character, Integer>(); // mark as visited: visited.put(vertexId, -1);

for (Map.Entry<Character, Set<Character>> entry: graph.entrySet()) {
char vertexId = entry.getKey();
if (!topologicalSort(vertexId, graph, sb, visited)) {
return "";
}
}

return sb.toString();
}

private void connectGraph(Map<Character, Set<Character>> graph, String prev, String curr) {
if (prev == null || curr == null) {
return;
}

int len = Math.min(prev.length(), curr.length());

for (int i = 0; i < len; i++) {
char p = prev.charAt(i);
char q = curr.charAt(i);
if (p != q) { // so if same duplicated work, will not reach here and not update graph
if (!graph.get(p).contains(q)) {
}
break;
}
}
}

private boolean topologicalSort(
char vertexId,
Map<Character, Set<Character>> graph,
StringBuffer sb,
Map<Character, Integer> visited
) {

if (visited.containsKey(vertexId)) {
// visited
if (visited.get(vertexId) == -1) { // -1 meaning visited, cycle found
return false;
}

if (visited.get(vertexId) == 1) {
return true;
}
}

visited.put(vertexId, -1); // mark as visited

Set<Character> neighbors = graph.get(vertexId);
for (char neighbor : neighbors) {
if (!topologicalSort(neighbor, graph, sb, visited)) {
return false;
}
}

sb.insert(0, vertexId);
visited.put(vertexId, 1); // restore visited

return true;
}
}
}

//////

class Solution {
public String alienOrder(String[] words) {
boolean[][] g = new boolean[26][26];
boolean[] s = new boolean[26];
int cnt = 0;
int n = words.length;
for (int i = 0; i < n - 1; ++i) {
for (char c : words[i].toCharArray()) {
if (cnt == 26) {
break;
}
c -= 'a';
if (!s[c]) {
++cnt;
s[c] = true;
}
}
int m = words[i].length();
for (int j = 0; j < m; ++j) {
if (j >= words[i + 1].length()) {
return "";
}
char c1 = words[i].charAt(j), c2 = words[i + 1].charAt(j);
if (c1 == c2) {
continue;
}
if (g[c2 - 'a'][c1 - 'a']) {
return "";
}
g[c1 - 'a'][c2 - 'a'] = true;
break;
}
}
for (char c : words[n - 1].toCharArray()) {
if (cnt == 26) {
break;
}
c -= 'a';
if (!s[c]) {
++cnt;
s[c] = true;
}
}

int[] indegree = new int[26];
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < 26; ++j) {
if (i != j && s[i] && s[j] && g[i][j]) {
++indegree[j];
}
}
}
for (int i = 0; i < 26; ++i) {
if (s[i] && indegree[i] == 0) {
q.offerLast(i);
}
}
StringBuilder ans = new StringBuilder();
while (!q.isEmpty()) {
int t = q.pollFirst();
ans.append((char) (t + 'a'));
for (int i = 0; i < 26; ++i) {
if (i != t && s[i] && g[t][i]) {
if (--indegree[i] == 0) {
q.offerLast(i);
}
}
}
}
return ans.length() < cnt ? "" : ans.toString();
}
}

• // OJ: https://leetcode.com/problems/alien-dictionary/
// Time: O(N)
// Space: O(1)
class Solution {
public:
string alienOrder(vector<string>& A) {
unordered_map<int, unordered_set<int>> G;
int indegree[26] = {};
for (auto &s : A) {
for (char c : s) G[c - 'a'] = {};
}
for (int i = 1; i < A.size(); ++i) {
int j = 0;
for (; j < min(A[i - 1].size(), A[i].size()); ++j) {
if (A[i - 1][j] == A[i][j]) continue;
G[A[i - 1][j] - 'a'].insert(A[i][j] - 'a');
break;
}
if (j == A[i].size() && j < A[i - 1].size()) return "";
}
for (auto &[from, tos] : G) {
for (int to : tos) {
indegree[to]++;
}
}
queue<int> q;
for (int i = 0; i < 26; ++i) {
if (G.count(i) && indegree[i] == 0) q.push(i);
}
string ans;
while (q.size()) {
int u = q.front();
q.pop();
ans += u + 'a';
for (int v : G[u]) {
if (--indegree[v] == 0) q.push(v);
}
}
return ans.size() == G.size() ? ans : "";
}
};

• '''
>>> a = ['a','b','c']
>>> zip(a, a[1:])
[('a', 'b'), ('b', 'c')]

# same as pairwise()
>>> from itertools import pairwise
>>> pairwise(a)
<itertools.pairwise object at 0x108458730>
>>> list(pairwise(a))
[('a', 'b'), ('b', 'c')]
'''

'''
>>> inDegree = {'a':11, 'b':22, 'c':33}

>>> [print(c) for c in inDegree.keys()]
a
b
c
[None, None, None]

# same as for c in inDegree.keys()
>>> [print(c) for c in inDegree]
a
b
c
[None, None, None]

>>> [print(c) for c in inDegree.values()]
11
22
33
[None, None, None]

>>> [print(c) for c in inDegree.items()]
('a', 11)
('b', 22)
('c', 33)
[None, None, None]
'''
from collections import defaultdict, deque
from typing import Dict, List, Set

class Solution:
def alienOrder(self, words: List[str]) -> str:
graph = defaultdict(set)
inDegree = defaultdict(int)

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

def _buildGraph(self, graph: Dict[str, Set[str]], words: List[str], inDegree: Dict[str, int]) -> None:
# Create a node for each character in each word
for word in words:
for c in word:
inDegree[c] = 0  # necessary for final char counting

for first, second in zip(words, words[1:]): # or pairwise(words)
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[v] += 1
break  # Later characters' order is meaningless
if j == length - 1 and len(first) > len(second):
# If 'ab' comes before 'a', it's an invalid order
graph.clear()
return

def _topology(self, graph: Dict[str, Set[str]], inDegree: Dict[str, int]) -> str:
result = ''
q = deque([c for c in inDegree if inDegree[c] == 0])

while q:
u = q.popleft()
result += u
for v in graph[u]:
inDegree[v] -= 1
if inDegree[v] == 0:
q.append(v)

# If there are remaining characters in inDegree, it means there's a cycle
if any(inDegree.values()):
return ''

# Words = ['z', 'x', 'y', 'x']
return result if len(result) == len(indegree) else ''

############

import collections

class Node(object):
def __init__(self, val):
self.val = val
self.neighbors = []

def connect(self, node):
self.neighbors.append(node)

def getNbrs(self):
return self.neighbors

class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""

def dfs(root, graph, visited):
visited[root] = 1
for nbr in graph[root].getNbrs():
if visited[nbr.val] == 0:
if not dfs(nbr.val, graph, visited):
return False
elif visited[nbr.val] == 1:
return False

visited[root] = 2
self.ans += root
return True

self.ans = ""
graph = {}
visited = collections.defaultdict(int)
self.topNum = 0
for i in range(0, len(words) - 1):
a = words[i]
b = words[i + 1]
i = 0
while i < len(a) and i < len(b):
if a[i] != b[i]:
nodeA = nodeB = None
if a[i] not in graph:
nodeA = Node(a[i])
graph[a[i]] = nodeA
else:
nodeA = graph[a[i]]
if b[i] not in graph:
nodeB = Node(b[i])
graph[b[i]] = nodeB
else:
nodeB = graph[b[i]]
nodeA.connect(nodeB)
break
i += 1
if i < len(a) and i >= len(b):
return ""

for c in graph:
if visited[c] == 0:
if not dfs(c, graph, visited):
return ""

unUsedSet = set()
for word in words:
for c in word: