269. Alien Dictionary

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:

1. You may assume all letters are in lowercase.

2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.

3. If the order is invalid, return an empty string.

4. There may be multiple valid order of letters, return any one of them is fine.

// BFS
string alienOrder(vector<string>& words) {
    set<pair<char, char> > st; // character relation pairs
    unordered_set<char> ch; // occurrence of letters
    vector<int> in(26, 0); // indegree
    queue<char> q; // BFS
    string res;
    for (string& w : words) ch.insert(w.begin(), w.end());
    for (int i = 0; i < words.size() - 1; ++i) {
        int len = min(words[i].length(), words[i + 1].length()), j = 0;
        for (; j < len; ++j) {
            if (words[i][j] != words[i + 1][j]) {
                st.insert(make_pair(words[i][j], words[i + 1][j]));
                break;
            }
        }
        if (j == len && words[i].length() > words[i + 1].length()) return res; // return empty string
    }
    for (auto& p : st) ++in[p.second - 'a'];
    for (auto& c : ch) {
        if (in[c - 'a'] == 0) {
            q.push(c);
            res += c;
        }
    }
    while (!q.empty()) {
        char c = q.front(); q.pop();
        for (auto& p : st) {
            if (p.first == c) {
                if (--in[p.second - 'a'] == 0) {
                    q.push(p.second);
                    res += p.second;
                }
            }
        }
    }
    return res.length() == ch.size() ? res : "";
}

// BFS
string alienOrder(vector<string>& words) {
    unordered_set<string> st; // hashset of strings with len = 2, str[0] -> str[1]
    unordered_set<char> ch; // occurrence of all characters
    vector<int> in(26, 0); // indegrees of each characters
    queue<char> q; // BFS queue
    string res; // final result
    // Add all chars in each word to ch
    for (const auto& word : words) ch.insert(word.begin(), word.end());
    // Find the character relations
    for (int i = 0; i < words.size() - 1; ++i) {
        int len = min(words[i].length(), words[i + 1].length()), j = 0;
        for (; j < len; ++j) {
            if (words[i][j] != words[i + 1][j]) {
                string tmp = string(2, ' ');
                tmp[0] = words[i][j];
                tmp[1] = words[i + 1][j];
                st.insert(tmp);
                break;
            }
        }
        if (j == len && words[i].length() > words[i + 1].length()) return res; // return empty string
    }
    // Calculate indegrees for each char
    for (const string& str : st) ++in[str[1] - 'a'];
    // Add char with 0 indegree to BFS queue
    for (const char& c : ch) {
        if (in[c - 'a'] == 0) {
            q.push(c);
            res += c;
        }
    }
    // BFS
    while (!q.empty()) {
        char c = q.front(); q.pop();
        for (const string& str : st) {
            if (str[0] == c) {
                if (--in[str[1] - 'a'] == 0) {
                    q.push(str[1]);
                    res += str[1];
                }
            }
        }
    }
    return res.length() == ch.size() ? res : "";
}

// BFS Topological Sort
string alienOrder(vector<string>& words) {
    string res;
    if (words.empty()) return res;
    unordered_map<char, unordered_set<char> > graph;
    unordered_map<char, int> indegree;
    // Initialization
    for (auto& word : words) {
        for (char ch : word) {
            indegree[ch] = 0;
        }
        
    }
    // Build adjacency list
    for (int i = 0; i < words.size() - 1; ++i) {
        string cur = words[i], next = words[i + 1];
        for (int j = 0; j < min(cur.length(), next.length()); ++j) {
            char c1 = cur[j], c2 = next[j];
            if (c1 != c2) {
                if (!graph[c1].count(c2)) {
                    graph[c1].insert(c2);
                    ++indegree[c2];
                }
                break;
            }
        }
    }
    // Use queue to do BFS
    queue<char> q;
    for (auto it = indegree.begin(); it != indegree.end(); ++it) {
        if (it->second == 0) {
            q.push(it->first);
        }
    }
    while (!q.empty()) {
        char c = q.front(); q.pop();
        res += c;
        for (auto it = graph[c].begin(); it != graph[c].end(); ++it) {
            if (--indegree[*it] == 0) {
                q.push(*it);
            }
        }
    }
    return (res.length() != indegree.size()) ? "" : res;
}

// DFS Topological Sort
bool dfs(vector<vector<bool> >& graph, vector<bool>& visited, int idx, string& res) {
    if (!graph[idx][idx]) return true;
    visited[idx] = true;
    for (int i = 0; i < 26; ++i) {
        if (i == idx || !graph[idx][i]) continue;
        if (visited[i] || !dfs(graph, visited, i, res)) return false;
    }
    visited[idx] = false;
    graph[idx][idx] = false;
    res += ('a' + idx);
    return true;
}
string alienOrder(vector<string>& words) {
    // graph[i][i] records occurrence of char i; graph[i][j] records the order pair
    vector<vector<bool> > graph(26, vector<bool>(26, false)); 
    vector<bool> visited(26, false);
    string res;
    // Record the occurrence of chars
    for (string& word : words) {
        for (char ch : word) {
            graph[ch - 'a'][ch - 'a'] = true;
        }
    }
    // Build letter order pairs
    for (int i = 0; i < words.size() - 1; ++i) {
        int len = min(words[i].length(), words[i + 1].length()), j = 0;
        for (; j < len; ++j) {
            if (words[i][j] != words[i + 1][j]) {
                graph[words[i][j] - 'a'][words[i + 1][j] - 'a'] = true;
                break;
            }
        }
        if (j == len && words[i].length() > words[i + 1].length()) return "";
    }
    // DFS
    for (int i = 0; i < 26; ++i) {
        if (!dfs(graph, visited, i, res)) return "";
    }
    reverse(res.begin(), res.end());
    return res;
}