Alien Dictionary Using Topological Sort

78k
0

Given a list of words sorted according to an alien language, return a string containing all unique characters in one valid alien dictionary order.

Adjacent words reveal ordering rules from the first position holding different characters. A longer word placed before an equal prefix word makes the dictionary invalid. Return an empty string for invalid input or for cyclic ordering rules.

Example 1

Input: words = ["wrt", "wrf", "er", "ett", "rftt"]

Output: "wertf"

Explanation: Adjacent comparisons give rules w -> e, e -> r, r -> t, and t -> f. One valid order becomes "wertf".

Example 2

Input: words = ["abc", "ab"]

Output: ""

Explanation: A longer word appears before an equal prefix word, so no valid alien dictionary order exists.

Approach 1

The alien dictionary problem can be represented as a directed graph where every unique character forms a node. For every adjacent word pair, the first mismatching characters create a precedence edge from the earlier word’s character to the later word’s character.

A three-state DFS distinguishes unvisited, active, and processed characters. Reaching an active character confirms a cycle, while adding characters after all outgoing neighbors produces a postorder whose reversal gives a valid alphabet order.

Algorithm

  • Initialize a graph and state map for every unique character, ensuring that characters without precedence relations also appear in the final order.

  • Compare every adjacent word pair and return an empty string when a longer earlier word contains the shorter later word as a complete prefix.

  • Locate the first mismatching character pair and add one directed edge from the earlier word’s character to the later word’s character.

  • Start DFS from every unvisited character, mark the current character active, and return failure upon reaching an active neighbor because a cycle prevents valid ordering.

  • After processing all outgoing neighbors, mark the current character finished and append the character to the postorder list.

  • Reverse the completed postorder and return the resulting alien alphabet order.

Dry Run

alien-dictionary-dfs-final-output-badge-corrected

alien-dictionary-dfs-final-output-badge-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Run DFS and detect back edge in directed graph.
bool dfs(char node, unordered_map<char, set<char>>& graph,
unordered_map<char, int>& state, string& order) {
// Active node means cycle in current recursion path.
if (state[node] == 1) {
return false;
}
// Processed node already has fixed postorder position.
if (state[node] == 2) {
return true;
}
// Mark node as active before exploring outgoing rules.
state[node] = 1;
// Visit every character forced after current character.
for (char nextChar : graph[node]) {
if (!dfs(nextChar, graph, state, order)) {
return false;
}
}
// Mark node as processed after all later characters.
state[node] = 2;
order.push_back(node);
return true;
}
public:
// Return a valid alien character order or empty string for invalid data.
string alienOrder(vector<string>& words) {
unordered_map<char, set<char>> graph;
unordered_map<char, int> state;
// Create graph node for every character.
for (string& word : words) {
for (char symbol : word) {
graph[symbol];
state[symbol] = 0;
}
}
// Build ordering rules from each adjacent pair.
for (int wordIndex = 0; wordIndex + 1 < (int)words.size(); wordIndex++) {
string first = words[wordIndex];
string second = words[wordIndex + 1];
int minLength = min(first.size(), second.size());
// Longer word before equal prefix creates invalid order.
if (first.size() > second.size() &&
first.substr(0, minLength) == second) {
return "";
}
// First different character gives one directed rule.
for (int pos = 0; pos < minLength; pos++) {
if (first[pos] != second[pos]) {
graph[first[pos]].insert(second[pos]);
break;
}
}
}
string order = "";
// Start DFS from every unprocessed character.
for (auto& entry : state) {
char node = entry.first;
if (state[node] == 0) {
if (!dfs(node, graph, state, order)) {
return "";
}
}
}
// DFS postorder gives reverse topological order.
reverse(order.begin(), order.end());
return order;
}
};
// Driver code.
int main() {
vector<string> words = {"wrt", "wrf", "er", "ett", "rftt"};
Solution sol;
cout << sol.alienOrder(words);
return 0;
}

Complexity Analysis

Time Complexity: O(C+U+E×log U) with ordered set or TreeSet adjacency, where C, U, and E denote input characters, unique characters, and extracted precedence relations; hash sets reduce the average bound to O(C+U+E).

Space Complexity: O(U+E), where the graph stores character nodes and precedence edges, while the state map, recursion stack, and answer require O(U) space.

Approach 2

Kahn’s Algorithm creates a topological ordering using character indegrees. Every character having indegree 0 has no unresolved precedence requirement and can appear next in the alien alphabet order.

Processing a character reduces the indegrees of outgoing neighbors. An answer containing fewer than all unique characters indicates a cycle, while ignoring duplicate edges prevents incorrect indegree values.

Algorithm

  • Initialize a graph and indegree map for every unique character, ensuring inclusion of characters having no precedence relations.

  • Compare every adjacent word pair and return an empty string for an invalid prefix case involving a longer earlier word and an identical shorter prefix.

  • Add an edge only for the first mismatching character pair and increase the destination indegree only when the edge is new.

  • Add every character having indegree 0 to a queue, since no preceding character is required.

  • Remove characters from the queue, append each character to the answer, and reduce outgoing-neighbor indegrees, adding a neighbor when the indegree becomes 0.

  • Return an empty string when the answer contains fewer than U characters; otherwise, return the completed alien alphabet order.

Note: Multiple valid alien alphabet orders may exist for some inputs. DFS and Kahn’s Algorithm can produce different correct orders as long as every extracted precedence relation is satisfied. An invalid prefix or directed cycle produces an empty string.

Dry Run

alien-dictionary-kahn-bfs-corrected

alien-dictionary-kahn-bfs-corrected

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Return a valid alien character order or empty string for invalid data.
string alienOrder(vector<string>& words) {
unordered_map<char, set<char>> graph;
unordered_map<char, int> indegree;
// Create graph node and indegree entry for every character.
for (string& word : words) {
for (char symbol : word) {
graph[symbol];
indegree[symbol] = 0;
}
}
// Build directed rules from adjacent sorted words.
for (int wordIndex = 0; wordIndex + 1 < (int)words.size(); wordIndex++) {
string first = words[wordIndex];
string second = words[wordIndex + 1];
int minLength = min(first.size(), second.size());
// Longer word before equal prefix creates invalid order.
if (first.size() > second.size() &&
first.substr(0, minLength) == second) {
return "";
}
// Add one unique edge from first mismatch.
for (int pos = 0; pos < minLength; pos++) {
if (first[pos] != second[pos]) {
if (graph[first[pos]].insert(second[pos]).second) {
indegree[second[pos]]++;
}
break;
}
}
}
queue<char> q;
// Push all characters without prerequisites.
for (auto& entry : indegree) {
if (entry.second == 0) {
q.push(entry.first);
}
}
string order = "";
// Remove zero-indegree characters level by level.
while (!q.empty()) {
char node = q.front();
q.pop();
order.push_back(node);
// Reduce indegree for every dependent character.
for (char nextChar : graph[node]) {
indegree[nextChar]--;
if (indegree[nextChar] == 0) {
q.push(nextChar);
}
}
}
// Missing characters in order means cycle.
if (order.size() != indegree.size()) {
return "";
}
return order;
}
};
// Driver code.
int main() {
vector<string> words = {"wrt", "wrf", "er", "ett", "rftt"};
Solution sol;
cout << sol.alienOrder(words);
return 0;
}

Complexity Analysis

Time Complexity: O(C+U+E×log U) with ordered set or TreeSet adjacency, where C, U, and E denote input characters, unique characters, and extracted precedence relations; hash sets reduce the average bound to O(C+U+E).

Space Complexity: O(U+E), where the graph stores character nodes and precedence edges, while the indegree map, queue, and answer require O(U) space.

Interview follow-up Questions

A longer word before an identical shorter prefix cannot be lexicographically sorted in any alphabet, so the answer must be empty.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: DisjointSet(int...

89.1k
Graph

Print Shortest Path

Input: n = 5, m = 6, edges = [[1,2,2],[2,5,5],[2,3,4],[1,4,1],[4,3,3],[3,5,1]] Output: [5,1,4,3,5] Explanation: Path 1->4->3->5 has total weight 1+3+1=5 , which is minimum. Input: n = 2, m = 0, edg...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return the minimum time...

81.2k
Comments0