C++ Topological sort easy to understand with comments/explanation + confusion clarification about ""


  • 0

    Key observation: each pair of adjacent words in dictionary actually defines exactly one relative order of a pair of letters, e.g.,

    • "dfujg" < "dfbtgdwf" implies that letter 'u' < 'b' in the alien alphabet,

    and that's all it implies, no less or no more, since pair ('u','b') is the first discrepancy pair.

    One issue about word1 being a prefix of another word2, actually, this problem has a hidden assumption that

    • "Empty letter" '' always comes before any letter instead of being treated as a regular letter just like others.

    I guess maybe it is better to clarify this assumption in the problem.

    Once all relative orders of pair of letters are collected, the rest letters shown in the dictionary are simply "free" letters with no order restriction indicated from the dictionary, so they can be put anywhere in the alien alphabet (I simply choose to attach to the end). The remaining work will be simply detect the current smallest letter from the "non-free" letters and insert to the front of alphabet.

        string alienOrder(vector<string>& ws) {
          unordered_set<char> free, nonfree; // free letters and letters with restricted order
          unordered_map<char, unordered_set<char>> less, greater;
          
          int n = ws.size(); if (!n) return "";
          for (int i = 1; i < n; ++i) {
            int nprev = ws[i-1].length(), ncur = ws[i].length();  
            int j = 0;
            while (j < min(nprev,ncur) && ws[i-1][j] == ws[i][j]) ++j; // find first discrepancy
            if (j < min(nprev,ncur)) { // insert into "edge"
              nonfree.insert(ws[i-1][j]); nonfree.insert(ws[i][j]);
              less[ws[i-1][j]].insert(ws[i][j]);
              greater[ws[i][j]].insert(ws[i-1][j]);
            }
            // hidden assumption: prefix must come before a word!
            else if (nprev > ncur) return "";
          }
          // remaining letters will be free letter
          for (auto& w:ws) for (char c:w) if (!nonfree.count(c)) free.insert(c); 
          
          string res;
          while (!nonfree.empty()) { // sort all nonfree letters
            char smallest = ' ';
            for (char c:nonfree) if (!greater.count(c)) { smallest = c; break; }
            if (smallest == ' ') return ""; // conflict detected if cannot find smallest letter
            res += smallest; nonfree.erase(smallest); // insert smallest letter to alphabet
            for (auto& p:less) { // remove smallest letter occurrences from each "edge"
              if (p.first == smallest) {
                for (auto& q:p.second) {
                  greater[q].erase(smallest); 
                  if (greater[q].empty()) greater.erase(q);      
                }  
                break;
              }
            }
            less.erase(smallest);
          }
          // simply attach free letter to the end
          for (char c:free) res += c; return res;
        }
    

Log in to reply
 

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