C++ solution, toposort + bit manipulation with comments

• ``````class Solution {
public:
string alienOrder(vector<string>& words) {
bitset<26> isExist;
vector<int> pres(26, 0); //pres contain the links pointing to former letters

for(int i=0; i<words.size(); i++) {
for(int j=0; j<words[i].size(); j++) {
isExist.set(words[i][j]-'a');
}
if (i >= 1) {
int pos = 0;
//looking at adjacent words, find the first different letter, form a link
while (pos < min(words[i].size(), words[i-1].size())) {
if(words[i][pos] != words[i-1][pos]) {
pres[words[i][pos]-'a'] |= (0x1 << (words[i-1][pos]-'a'));
//set the nth bit to 1 if there is a link
break;
}
pos++;
}
}
}

//topological sort
string res = "";
while(isExist.count()) {
bool flag = true;
for(int j=0; j<26; j++) {
if (isExist.test(j) && pres[j] == 0) {
flag = false;
isExist.set(j, 0);
res += ('a' + j);
for(int k=0; k<26; k++) {
pres[k] &= ~(0x1 << (j)); //clear links pointing to j
}
}
}
if (flag) return ""; //no progress! There is a circle!
}
return res;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.