Table of Contents
Given a list of words sorted in a special alien language, find the order of characters in that language.
The alien language is represented by a list of words where each word consists of lowercase letters. However, the order of the letters in the alien language is unknown.
You need to determine the order of characters in the alien language based on the given list of words.
Example:
Input:
words = ["wrt", "wrf", "er", "ett", "rftt"]
Explanation: The given words are sorted in the alien language as follows:
w -> e -> r
| | |
v t f
| | |
t t t
| | |
r f t
Output:
"wertf"
Input:
words = ["z", "x"]
Explanation: The given words are sorted in the alien language as follows:
z -> x
Output:
"zx"
Input:
words = ["z", "x", "z"]
Explanation: The given words have duplicate entries, but the result can still be determined. In this case, the order of characters in the alien language is not well-defined, and we return an empty string.
Output:
""
Time Complexity:
The time complexity of the solution is O(C), where C is the total number of characters in the input words.
Space Complexity:
The space complexity of the solution is O(V + E), where V is the number of unique characters in the input words, and E is the number of relationships (edges) between the characters.
Alien Dictionary C++ program:
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <queue>
#include <iostream>
using namespace std;
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> graph; // Adjacency list representation of the graph
unordered_map<char, int> inDegree; // In-degree of each character
// Initialize in-degree for all characters to 0
for (const string& word : words) {
for (char c : word) {
inDegree[c] = 0;
}
}
// Build the graph and calculate in-degree for each character
for (int i = 1; i < words.size(); i++) {
string word1 = words[i - 1];
string word2 = words[i];
int len = min(word1.length(), word2.length());
for (int j = 0; j < len; j++) {
char parent = word1[j];
char child = word2[j];
if (parent != child) {
// Add the relationship parent -> child in the graph
if (graph[parent].find(child) == graph[parent].end()) {
graph[parent].insert(child);
inDegree[child]++;
}
break;
}
}
}
string result;
queue<char> q;
// Add all characters with in-degree 0 to the queue
for (const auto& entry : inDegree) {
if (entry.second == 0) {
q.push(entry.first);
}
}
while (!q.empty()) {
char currentChar = q.front();
q.pop();
result += currentChar;
// Process all children (outgoing edges)
for (char child : graph[currentChar]) {
inDegree[child]--; // Reduce the in-degree of the child
// If the child now has in-degree 0, add it to the queue
if (inDegree[child] == 0) {
q.push(child);
}
}
}
// If the size of the result is not equal to the number of unique characters,
// it means there is a cycle in the graph, and the order cannot be determined.
if (result.length() != inDegree.size()) {
return "";
}
return result;
}
int main() {
vector<string> words1 = {"wrt", "wrf", "er", "ett", "rftt"};
vector<string> words2 = {"z", "x"};
vector<string> words3 = {"z", "x", "z"};
cout << alienOrder(words1) << endl; // Output: "wertf"
cout << alienOrder(words2) << endl; // Output: "zx"
cout << alienOrder(words3) << endl; // Output: ""
return 0;
}
Explanation of Code:
The alienOrder function takes a vector of words as input and determines the order of characters in the alien language. It builds a graph by comparing adjacent words, calculates in-degrees for each character, and performs topological sorting using BFS. The function returns the order of characters in the alien language or an empty string if there is a cycle in the graph.