-
Notifications
You must be signed in to change notification settings - Fork 0
/
alien_dictionary.cpp
100 lines (88 loc) · 2.28 KB
/
alien_dictionary.cpp
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//{ Driver Code Starts
// Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
// } Driver Code Ends
// User function Template for C++
class Solution{
public:
string findOrder(string dict[], int N, int K) {
vector<int>adj[K];
//creating adjacency list
for(int i=0;i<N-1;i++){
string s1=dict[i];
string s2=dict[i+1];
int len=min(s1.length(),s2.length());
for(int ptr=0;ptr<len;ptr++){
if(s1[ptr]!=s2[ptr]){
adj[s1[ptr]-'a'].push_back(s2[ptr]-'a');
break;
}
}
}
vector<int> indegree(K,0);
for(int i=0;i<K;i++){
for(auto it:adj[i]){
indegree[it]++;
}
}
vector<int>topo;
queue<int>q;
for(int i=0;i<K;i++){
if(indegree[i]==0)q.push(i);
}
while(!q.empty()){
int node=q.front();
q.pop();
topo.push_back(node);
for(auto it:adj[node]){
indegree[it]--;
if(indegree[it]==0)q.push(it);
}
}
string ans="";
for(auto it:topo){
ans=ans+char(it+'a');
}
return ans;
}
};
//{ Driver Code Starts.
string order;
bool f(string a, string b) {
int p1 = 0;
int p2 = 0;
for (int i = 0; i < min(a.size(), b.size()) and p1 == p2; i++) {
p1 = order.find(a[i]);
p2 = order.find(b[i]);
// cout<<p1<<" "<<p2<<endl;
}
if (p1 == p2 and a.size() != b.size()) return a.size() < b.size();
return p1 < p2;
}
// Driver program to test above functions
int main() {
int t;
cin >> t;
while (t--) {
int N, K;
cin >> N >> K;
string dict[N];
for (int i = 0; i < N; i++) cin >> dict[i];
Solution obj;
string ans = obj.findOrder(dict, N, K);
order = "";
for (int i = 0; i < ans.size(); i++) order += ans[i];
string temp[N];
std::copy(dict, dict + N, temp);
sort(temp, temp + N, f);
bool f = true;
for (int i = 0; i < N; i++)
if (dict[i] != temp[i]) f = false;
if(f)cout << 1;
else cout << 0;
cout << endl;
}
return 0;
}
// } Driver Code Ends