Problem
You are given a list of words sorted according to the rules of an alien language. The language uses lowercase English letters, but their alphabetical order is unknown.Return a valid ordering of the characters. If no valid ordering exists, return an empty string.
The character order is determined by comparing adjacent words. The first different character between two words tells us which character must come before the other.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
words = ["wrt","wrf","er","ett","rftt"]Output
"wertf"Solution
This problem can be solved using Breadth-First Search (BFS) with Kahn's Algorithm for topological sorting. Each character is treated as a node, and the ordering rules between characters form directed edges.We first add every character from all words to the graph. Then, we compare every pair of adjacent words and find the first position where their characters differ.
If two characters differ, an ordering relationship is created. For example, comparing
"wrt" and "wrf" gives t → f, meaning t must come before f. Only the first different character matters.
There is one special invalid case. If a longer word appears before its exact prefix, such as
["abc","ab"], no valid character ordering exists.
We also maintain the in-degree of every character. The in-degree represents how many characters must come before it. All characters with an in-degree of
0 have no remaining dependencies, so they are added to a queue.
We repeatedly remove a character from the queue, add it to the result, and reduce the in-degree of its neighbors. When a neighbor's in-degree becomes
0, it is added to the queue.
If all characters are processed, a valid ordering exists. If some characters remain unprocessed, the graph contains a cycle, so an empty string is returned.
public String alienOrder(String[] words) {
Map<Character, List<Character>> graph = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();
// Add all characters.
for (String word : words) {
for (char ch : word.toCharArray()) {
graph.putIfAbsent(ch, new ArrayList<>());
inDegree.putIfAbsent(ch, 0);
}
}
// Build ordering relationships.
for (int i = 0; i < words.length - 1; i++) {
String first = words[i];
String second = words[i + 1];
// Invalid prefix case.
if (first.length() > second.length() &&
first.startsWith(second)) {
return "";
}
int length = Math.min(first.length(), second.length());
for (int j = 0; j < length; j++) {
char from = first.charAt(j);
char to = second.charAt(j);
if (from != to) {
graph.get(from).add(to);
inDegree.put(to, inDegree.get(to) + 1);
break;
}
}
}
Queue<Character> queue = new LinkedList<>();
// Add characters with no prerequisites.
for (char ch : inDegree.keySet()) {
if (inDegree.get(ch) == 0) {
queue.offer(ch);
}
}
StringBuilder result = new StringBuilder();
while (!queue.isEmpty()) {
char ch = queue.poll();
result.append(ch);
// Remove this character as a dependency.
for (char neighbor : graph.get(ch)) {
inDegree.put(neighbor, inDegree.get(neighbor) - 1);
if (inDegree.get(neighbor) == 0) {
queue.offer(neighbor);
}
}
}
return result.length() == graph.size()
? result.toString()
: "";
}
Complexity
LetV be the number of unique characters and E be the number of ordering relationships. Building the graph and processing each character and relationship takes O(V + E) time.
The graph, in-degree map, queue, and result require
O(V + E) space.
DFS Approach
The problem can also be solved using Depth-First Search (DFS) for topological sorting.A character currently in the DFS path is marked as visiting. If DFS reaches another character that is already being visited, the graph contains a cycle, so no valid ordering exists.
After processing all neighbors, the character is added to the result. The final result is reversed to obtain the correct ordering.
public String alienOrder(String[] words) {
Map<Character, List<Character>> graph = new HashMap<>();
// Add all characters to the graph.
for (String word : words) {
for (char ch : word.toCharArray()) {
graph.putIfAbsent(ch, new ArrayList<>());
}
}
// Build ordering relationships.
for (int i = 0; i < words.length - 1; i++) {
String first = words[i];
String second = words[i + 1];
// Invalid prefix case.
if (first.length() > second.length() &&
first.startsWith(second)) {
return "";
}
int length = Math.min(first.length(), second.length());
for (int j = 0; j < length; j++) {
if (first.charAt(j) != second.charAt(j)) {
graph.get(first.charAt(j))
.add(second.charAt(j));
break;
}
}
}
Set<Character> visited = new HashSet<>();
Set<Character> visiting = new HashSet<>();
StringBuilder result = new StringBuilder();
for (char ch : graph.keySet()) {
if (hasCycle(ch, graph, visited, visiting, result)) {
return "";
}
}
return result.reverse().toString();
}
private boolean hasCycle(char ch,
Map<Character, List<Character>> graph,
Set<Character> visited,
Set<Character> visiting,
StringBuilder result) {
// Found a cycle.
if (visiting.contains(ch)) {
return true;
}
// Already processed.
if (visited.contains(ch)) {
return false;
}
visiting.add(ch);
for (char neighbor : graph.get(ch)) {
if (hasCycle(neighbor, graph, visited, visiting, result)) {
return true;
}
}
visiting.remove(ch);
visited.add(ch);
// Add after processing dependencies.
result.append(ch);
return false;
}
Complexity
Building the graph and performing DFS takesO(V + E) time. The graph, visited sets, recursion stack, and result require O(V + E) space.