[Geeks for Geeks] Alien Dictionary

Alien Dictionary

Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary. Find the order of characters in the alien language.
Note: Many orders may be possible for a particular test case, thus you may return any valid order and output will be 1 if the order of string returned by the function is correct else 0 denoting incorrect string returned.

  • Time : O(n * maxlength(s) + k)
  • Space : O(k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution{
pair<char, char> order(string& a, string& b) {
int i = 0, j = 0, n = a.length(), m = b.length();
while(i < n and j < m) {
if(a[i] == b[j]) i++,j++;
else return {a[i], b[j]};
}
return {'#', '#'};
}
public:
string findOrder(string dict[], int N, int K) {
unordered_map<char, int> ind;
unordered_map<char, vector<char>> adj;
for(int i = 0; i < N - 1; i++) {
pair<char, char> p = order(dict[i], dict[i + 1]);
char front = p.first, back = p.second;
if(front == '#') continue;
ind[back] += 1;
ind[front] += 0;
adj[front].push_back(back);
}
queue<char> q;
string res = "";
for(auto& p : ind) {
char ch = p.first;
int deg = p.second;
if(deg) continue;
q.push(ch);
res.push_back(ch);
}
while(!q.empty()) {
auto u = q.front(); q.pop();
for(auto& v : adj[u]) {
if(--ind[v] == 0) {
q.push(v);
res.push_back(v);
}
}
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/15/PS/GeeksforGeeks/alien-dictionary/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.