vivek_ragi

ALIEN_DICTIONARY

Jun 19th, 2021 (edited)
722
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     unordered_map<char, vector<char>> adj;
  4.     set<char> s;
  5.     unordered_map<char, int> color;
  6.     unordered_map<char, int> vis;
  7.    
  8.     bool detectCycle(char itr) {
  9.         color[itr] = 1; // being visited
  10.        
  11.         for(auto c: adj[itr]) {
  12.             if(color[c] == 1) {
  13.                 return true; // backedge
  14.             }
  15.            
  16.             if(color[c] == 0 and detectCycle(c)) {
  17.                 return true; //self - loop
  18.             }
  19.         }
  20.         color[itr] = 2; // processed
  21.        
  22.         return false;
  23.     }
  24.    
  25.    
  26.     void topo(stack<char> &st, char itr) {
  27.         vis[itr] = true;
  28.        
  29.         for(char c: adj[itr]) {
  30.             if(!vis[c]) {
  31.                 topo(st, c);
  32.             }
  33.         }
  34.         st.push(itr);
  35.     }
  36.    
  37.     string alienOrder(vector<string>& W) {
  38.         int n = W.size();
  39.        
  40.         //construcitng a graph for performing topo sort
  41.        
  42.         for(string str: W) {
  43.             for(char c: str) {
  44.                 s.insert(c);
  45.                 color[c] = 0;
  46.             }
  47.         }
  48.        
  49.         for(int i = 0; i < n - 1; ++i) {
  50.             int min_len = min(W[i].size(),W[i + 1].size());
  51.            
  52.            
  53.             if(W[i].size() > W[i + 1].size() and W[i].substr(0,min_len) == W[i + 1].substr(0,min_len)) {
  54.                 return "";
  55.             }
  56.            
  57.             for(int j = 0; j < min_len; ++j) {
  58.                 if(W[i][j] != W[i + 1][j]) {
  59.                     adj[W[i][j]].push_back(W[i + 1][j]);
  60.                     break;
  61.                 }
  62.             }
  63.         }
  64.        
  65.        
  66.         // for(auto c: adj) {
  67.         //     cout << c.first << " ";
  68.         //     for(auto cc: c.second) {
  69.         //         cout << cc << " ";
  70.         //     }
  71.         //     cout << "\n";
  72.         // }
  73.        
  74.        
  75.         //graph has been constructed, now do topo sort
  76.        
  77.         //first check if it has a cycle
  78.        
  79.         //if not then order the vertices in a usual topo manner
  80.        
  81.        
  82.         // vertices will be in s
  83.         // 0 --- unvisited
  84.         // 1 ---- being visited
  85.         // 2 ------ visited and processes
  86.         for(auto it : s) {
  87.             vis[it] = 0;
  88.             if(color[it] == 0) {
  89.                 if(detectCycle(it)) {
  90.                     return "";
  91.                 }
  92.             }
  93.         }
  94.        
  95.         stack<char> st;
  96.        
  97.        
  98.         for(auto it : s) {
  99.             if(vis[it] == 0) {
  100.                 topo(st,it);
  101.             }
  102.         }
  103.        
  104.         string ans = "";
  105.        
  106.         while(!st.empty()) {
  107.             ans += st.top();
  108.             st.pop();
  109.         }
  110.        
  111.        
  112.         return ans;
  113.        
  114.     }
  115. };
RAW Paste Data