DSA
Alien Dictionary
Graphs problem — solution with code and analysis.
Given a sorted dictionary of an alien language having some words dict and k starting alphabets of a standard dictionary. Find the order of characters in the alien language. If no valid ordering of letters is possible, then return an empty string.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be "true" if the order of string returned by the function is correct else "false" denotes incorrect string returned.
Practice Link
Sample#
Input: dict[] = ["baa","abcd","abca","cab","cad"], k = 4 Output: true Explanation: order -> b, d, a, c
Intiution#
We need to find the order of characters, which comes before which character. Sounds like a topological sort. Hard part is to create the directed graph from the dictionary given. Hint: Consider two consecutive words in a dictionary, and decide why the first one comes before the latter (compare the differentiating character among the two words).
Approach#
- Creating AdjList
- Loop though the dictionary and pick two consecutive words at a time.
- Out of two words, find the differentiating character (lets say at diffIdx).
- wordA[diffIdx] -> wordB[diffIdx]
- Also store the inDegrees of the characters.
- Do standard topological sort and store the order of characters.
Implementation#
void createAdjListAndIndegree(vector<string> dict, vector<vector<int>> &adj, vector<int> &inDegree)
{
int size = dict.size();
for(int i=0;i<size-1;i++)
{
string wordA = dict[i];
string wordB = dict[i+1];
int minSize = min(wordA.length(), wordB.length());
for(int i=0;i<minSize;i++)
{
if(wordA[i] != wordB[i])
{
adj[wordA[i] - 'a'].push_back(wordB[i] - 'a');
inDegree[wordB[i] - 'a']++;
break;
}
}
}
}
string findOrder(vector<string> dict, int k) {
vector<vector<int>> adj(k);
vector<int> inDegree(k);
createAdjListAndIndegree(dict, adj, inDegree);
queue<int> q;
string result="";
for(int i=0;i<k;i++)
{
if(inDegree[i]==0)
q.push(i);
}
while(!q.empty())
{
int topChar = q.front();
q.pop();
for(auto nextChar: adj[topChar])
{
inDegree[nextChar]--;
if(inDegree[nextChar]==0)
q.push(nextChar);
}
result+=topChar+'a';
}
return result;
}
LeetCode Variant (LC 269)#
The LeetCode version changes two things:
- The alphabet size is unknown — you must infer unique characters from the words themselves.
- Invalid inputs must be detected: a cycle in the ordering graph, or a word that is a prefix of an earlier word (e.g. ["abc", "ab"]) → return "".
Approach#
Same Kahn's BFS topological sort, with two extra steps:
- Collect unique characters from all words into a set — these are your graph nodes.
- Detect invalid prefix: if words[i] is longer than words[i+1] and they share the same prefix up to words[i+1].size(), the ordering is impossible.
- Detect cycle: after BFS, if any character is still in the set (not processed), a cycle exists → return "".
Common Bugs to Watch#
| Bug | Wrong | Correct |
|---|---|---|
| Comparing wrong word | words[i][j+1] | words[i+1][j] |
| Off-by-'a' in BFS | inDegree[next]-- | inDegree[next-'a']-- |
| Type mismatch | vector<int> temp = x.second | auto temp = x.second |
Implementation#
class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, vector<char>> adjList;
unordered_set<char> st;
// collect all unique characters
for (auto& word : words)
for (char c : word)
st.insert(c);
// build edges from adjacent word pairs
for (int i = 0; i < (int)words.size() - 1; i++) {
int len = min(words[i].size(), words[i + 1].size());
bool edgeAdded = false;
for (int j = 0; j < len; j++) {
if (words[i][j] != words[i + 1][j]) {
adjList[words[i][j]].push_back(words[i + 1][j]);
edgeAdded = true;
break;
}
}
// "abc" before "ab" is invalid
if (!edgeAdded && words[i].size() > words[i + 1].size())
return "";
}
vector<int> inDegree(26, 0);
for (auto& [src, neighbors] : adjList)
for (char c : neighbors)
inDegree[c - 'a']++;
queue<char> q;
for (int i = 0; i < 26; i++)
if (st.count(i + 'a') && inDegree[i] == 0)
q.push(i + 'a');
string result;
while (!q.empty()) {
char curr = q.front(); q.pop();
result += curr;
st.erase(curr);
for (char next : adjList[curr]) {
inDegree[next - 'a']--;
if (inDegree[next - 'a'] == 0)
q.push(next);
}
}
// cycle detected if any character was never processed
return st.empty() ? result : "";
}
};
Complexity Analysis#
| Complexity | Reason | |
|---|---|---|
| Time | O(N · L) | Scanning all characters in all words dominates; graph ops are O(U²) ≤ O(676) = O(1) |
| Space | O(U²) = O(1) | Adj list holds at most U² edges; all other structures are O(U) — U ≤ 26 |
Where N = number of words, L = average word length, U = number of unique characters (≤ 26).