269. Alien Dictionary (Hard)

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 words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example,
Given the following words in dictionary,

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

The correct order is: "wertf".

Note:

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

Solution 1: Topological Sort, BFS

这道题让给了我们一些按“字母顺序”排列的单词，但是这个字母顺序不是我们熟知的顺序，而是另类的顺序，让我们根据这些“有序”的单词来找出新的字母顺序，这实际上是一道有向图的问题，跟之前的那两道Course Schedule II和Course Schedule的解法很类似，我们先来看BFS的解法，我们需要一个set来保存我们可以推测出来的顺序关系，比如题目中给的例子，我们可以推出的顺序关系有：

t->f
w->e
r->t
e->r

那么set就用来保存这些pair，我们还需要另一个set来保存所有出现过的字母，需要一个一维数组in来保存每个字母的入度，另外还要一个queue来辅助拓扑遍历，我们先遍历单词集，把所有字母先存入ch，然后我们每两个相邻的单词比较，找出顺序pair，然后我们根据这些pair来赋度，我们把ch中入度为0的字母都排入queue中，然后开始遍历，如果字母在set中存在，则将其pair中对应的字母的入度减1，若此时入度减为0了，则将对应的字母排入queue中并且加入结果res中，直到遍历完成，我们看结果res和ch中的元素个数是否相同，若不相同则说明可能有环存在，返回空字符串，参见代码如下：

version 1: 9ms

class Solution {
public:
    string alienOrder(vector<string>& words) {
        if (words.size() == 1) return words[0];
        set<pair<char,char>> s;
        unordered_set<char> ch;

        for (auto w:words) ch.insert(w.begin(), w.end());
        for (int i = 1; i < words.size(); ++i) {
            string s1 = words[i-1], s2 = words[i];
            int n = min(s1.size(), s2.size()), j = 0;
            for (; j < n; ++j) {
                if (s1[j] != s2[j]) {
                    s.insert({s1[j],s2[j]});
                    break;
                }
            }
            if (j == n && s1.size() > s2.size()) return "";
        }
        vector<int> in(26, 0);
        for (auto& c:s) ++in[c.second-'a'];

        string res;
        queue<char> q;
        for (auto& c:ch) {
            if (in[c-'a'] == 0) q.push(c);
        }

        while (!q.empty()) {
            char key = q.front(); q.pop();
            res += key;
            for (auto c: s) {
                if (c.first == key) {
                    if (--in[c.second-'a'] == 0) {
                        q.push(c.second);
                    }
                }
            }
        }

        return res.size() == ch.size() ? res:"";

    }
};

version 2: 6ms

class Solution {
public:
    string alienOrder(vector<string>& words) {
        if (words.size() == 1) return words[0];
        unordered_map<char,set<char>> m;
        unordered_set<char> ch;
        vector<int> in(26, 0);
        for (auto w:words) ch.insert(w.begin(), w.end());
        for (int i = 1; i < words.size(); ++i) {
            string s1 = words[i-1], s2 = words[i];
            int n = min(s1.size(), s2.size()), j = 0;
            for (; j < n; ++j) {
                if (s1[j] != s2[j]) {
                    if (!m.count(s1[j]) || !m[s1[j]].count(s2[j])) {
                        m[s1[j]].insert(s2[j]);
                        ++in[s2[j]-'a'];
                    }
                    break;
                }
            }
            if (j == n && s1.size() > s2.size()) return "";
        }

        string res;
        queue<char> q;
        for (auto& c:ch) {
            if (in[c-'a'] == 0) q.push(c);
        }

        while (!q.empty()) {
            char key = q.front(); q.pop();
            res += key;
            for (char c: m[key]) {
                if (--in[c-'a'] == 0) {
                        q.push(c);
                }
            }
        }

        return res.size() == ch.size() ? res:"";

    }
};

Solution 2: DFS

下面来看一种DFS的解法，思路和BFS的很类似，我们需要建立一个二维的bool数组g，然后把出现过的字母的对应的位置都赋为true，然后我们把可以推出的顺序的对应位置也赋为true，然后我们就开始递归调用，如果递归函数有返回false的，说明有冲突，则返回false，递归调用结束后结果res中存了入度不为0的字母，最后把入度为0的字母加到最后面，最后把结果res翻转一下即可，参见代码如下：