C++ solution, toposort + bit manipulation with comments


  • 0
    D
    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;
    }
    };

Log in to reply
 

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