269. Alien Dictionary --------H

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:

Input:
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Output: "wertf"

Example 2:

Input:
[
  "z",
  "x"
]

Output: "zx"

Example 3:

Input:
[
  "z",
  "x",
  "z"
] 

Output: "" 

Explanation: The order is invalid, so return "".

Note:

• You may assume all letters are in lowercase.
• If the order is invalid, return an empty string.
• There may be multiple valid order of letters, return any one of them is fine.

A:

topological sort

比较tricky的地方，toplogical sort的时候， 如果找到的是GRAY node, 则返回 false.

class Solution {
public:
    string alienOrder(vector<string>& words) {
        int n = words.size();
        // toplogical sort
        unordered_map<char, int> colors;// WHITE, GRAY, BLACK
        for(int i =0;i<n;i++){
            for(char ch : words[i])
                colors[ch] = WHITE;// not visited
        }
        // build edges
        unordered_map<char, vector<char>> edges;
        for(int i =0;i<n-1;i++){
            string s1 = words[i];
            string s2 = words[i+1];
            int n1 = s1.length(), n2 = s2.length();
            for(int j = 0;j< min(n1,n2); j++){
                char c1 = s1[j];
                char c2 = s2[j];
                if(c1 != c2){
                    edges[c1].push_back(c2);
                    break;
                }else if(n1 > n2 && j == n2-1){// s1=="ab", s2 = "a"-->false; as "b" canot go before ""
                    return "";
                }
            }
        }
        string res= "";       
        for(auto it : colors){ // dfs 
            if(it.second==WHITE){
                if( dfs_visit(it.first, colors, edges, res))//if found circular
                    return "";
            }
        }
        return res;
    }
private:
    enum COLOR { WHITE=0, GRAY, BLACK};
    bool dfs_visit(char ch,   unordered_map<char, int> & colors, unordered_map<char, vector<char>> &edges, string &res){
        colors[ch] = GRAY;
        for(char nextCh : edges[ch]){
            if(colors[nextCh]==GRAY){
                return true;   // find circular 
            }else if(colors[nextCh] == WHITE){
                if(dfs_visit(nextCh, colors, edges, res)){
                    return true;  // find circular 
                }
            }
        }
        colors[ch] = BLACK;
        res = string(1,ch)+res;
        return false;
    }
};

Mistakes:

为了处理["abc", "ab"]  ，返回应该是 "";       因为“b“ 不能在”“ 前面。