C++ BFS/Topsort Solution with both "words" and "each word" in lexicological order perspective


  • 0
    X

    I've spent hours thinking where I might be wrong until I found a totally wrong direction of the original question, even though they totally shared the same idea and take advantage of an easy topological sorting algorithm... The only difference lies in how we construct the dependency graph:

    • (Original question) words are sorted lexicographically by the rules of this new language
    • (My misunderstanding/Variation) each given string represents a lexicographical order

    Other than the graph construction, the whole sorting process is exactly the same.
    Here are the AC code that runs 6ms:

    class Solution {
    public:
        string alienOrder(vector<string>& words) {
            int n = words.size(); 
            
            map<char, vector<char>> g;
            map<char, int> degrees; 
            for (string word : words)
                for (char letter : word)
                    degrees[letter] = 0;
            
           //======Construct Dependency Graph=============
             for (int i = 0; i < n - 1; i++) {
                string s1 = words[i];
                string s2 = words[i + 1];
                for (int j = 0; j < min(s1.size(), s2.size()); j++) {
                    if (s1[j] != s2[j]) { //from s2[j] to s1[j]
                        g[s1[j]].push_back(s2[j]);
                        degrees[s2[j]]++;
                        break;
                    }
                }
            }
            //=============================================
    
            //topology sort
            queue<char> untaken; //holding points with 0 in-degree
            for (auto item : degrees){
                if (item.second == 0)
                    untaken.push(item.first);
            }
            
            string res;
            while (!untaken.empty()) {
                //remove v from untaken
                char v = untaken.front();
                untaken.pop();
                if (res.find(v) == std::string::npos)
                    res.push_back(v);
                
                //remove all edges starting with v 
                //and decrease the ending points' degree
                while (!g[v].empty()) {
                    char dest = g[v].back();
                    g[v].pop_back();
                    if (--degrees[dest] == 0)
                        untaken.push(dest);
                }
            }
    
            if (res.size() != degrees.size()) return "";  //exsist cycle
            else return res;
        }
    };
    

    For the second thought, the construction part will be:

    //==========Construct Dependency Graph=============
    for (int j = 1; j < s.size(); j++) { //from s[j] to s[j - 1]
        vector<char> tmp = g[s[j]];
        if (s[j] == s[j - 1] || 
              find(tmp.begin(), tmp.end(), s[j - 1]) != tmp.end())
            continue;
        g[s[j]].push_back(s[j - 1]);
        degrees[s[j - 1]]++;
    }
    //==============================================                      
    

    Hope it helps if you have the same confusion.


  • 0
    Z

    Dude, I was stuck for the same reason.
    It was so embarrassing that I didn't even look at the given EXAMPLE...


Log in to reply
 

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