mirror of https://github.com/doocs/leetcode.git
56 lines
1.7 KiB
C++
56 lines
1.7 KiB
C++
class Solution {
|
|
public:
|
|
string alienOrder(vector<string>& words) {
|
|
vector<vector<bool>> g(26, vector<bool>(26));
|
|
vector<bool> s(26);
|
|
int cnt = 0;
|
|
int n = words.size();
|
|
for (int i = 0; i < n - 1; ++i) {
|
|
for (char c : words[i]) {
|
|
if (cnt == 26) break;
|
|
c -= 'a';
|
|
if (!s[c]) {
|
|
++cnt;
|
|
s[c] = true;
|
|
}
|
|
}
|
|
int m = words[i].size();
|
|
for (int j = 0; j < m; ++j) {
|
|
if (j >= words[i + 1].size()) return "";
|
|
char c1 = words[i][j], c2 = words[i + 1][j];
|
|
if (c1 == c2) continue;
|
|
if (g[c2 - 'a'][c1 - 'a']) return "";
|
|
g[c1 - 'a'][c2 - 'a'] = true;
|
|
break;
|
|
}
|
|
}
|
|
for (char c : words[n - 1]) {
|
|
if (cnt == 26) break;
|
|
c -= 'a';
|
|
if (!s[c]) {
|
|
++cnt;
|
|
s[c] = true;
|
|
}
|
|
}
|
|
vector<int> indegree(26);
|
|
for (int i = 0; i < 26; ++i)
|
|
for (int j = 0; j < 26; ++j)
|
|
if (i != j && s[i] && s[j] && g[i][j])
|
|
++indegree[j];
|
|
queue<int> q;
|
|
for (int i = 0; i < 26; ++i)
|
|
if (s[i] && indegree[i] == 0)
|
|
q.push(i);
|
|
string ans = "";
|
|
while (!q.empty()) {
|
|
int t = q.front();
|
|
ans += (t + 'a');
|
|
q.pop();
|
|
for (int i = 0; i < 26; ++i)
|
|
if (i != t && s[i] && g[t][i])
|
|
if (--indegree[i] == 0)
|
|
q.push(i);
|
|
}
|
|
return ans.size() < cnt ? "" : ans;
|
|
}
|
|
}; |