269. Alien Dictionary解题报告

Description:

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.

Note:
You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.

Example:

Example 1:

Given the following words in dictionary,

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
The correct order is: "wertf".

Example 2:

Given the following words in dictionary,

[
  "z",
  "x"
]
The correct order is: "zx".

Example 3:

Given the following words in dictionary,

[
  "z",
  "x",
  "z"
]
The order is invalid, so return "".

Link:

https://leetcode.com/problems/alien-dictionary/description/

解题方法：

这是一道图求环的题。
第一步：
直接遍历输入数组，从每两个相连的单词查找已有的先后顺序信息。
例如：abc, abd
可以得出：c > d
因为输入的单词是由词典顺序排序的，所以不会存在不相邻的两个单词也有必要的顺序信息。
将得到的信息存在哈希表里。
第二步：
对图进行求环，这里我用的是DFS的方法，虽然BFS更快，但是这道题决定时间复杂度的在于遍历单词的每个字母。
在DFS的同时计算每个单词依照语言顺序后面有多少个字母。（用hash_set来统计）
如果图中有环，说明有冲突，没有一个有效的字母顺序。
如果有字母存在相同的统计结果，我们只要输出其中的一种。
第三步：
对以上统计结果（字母-->该字母依照语言顺序后面有多少个字母）排序（降序），求出结果即为我们需要的结果。

Tips:

Time Complexity：

O(N) N为所有单词所有字母的总和

完整代码：

string alienOrder(vector<string>& words) {
    int len = words.size();
    if(!len)
        return "";
    if(len == 1)
        return words[0];
    //get rules between two characters (build Graph)
    unordered_map<char, unordered_set<char>> characters;
    for(int i = len - 1; i > 0; i--) {
        string str2 = words[i];
        string str1 = words[i - 1];
        for(char cha: str1)
            if(characters.find(cha) == characters.end())
                characters[cha] = unordered_set<char>();
        for(char cha: str2)
            if(characters.find(cha) == characters.end())
                characters[cha] = unordered_set<char>();
        for(int i = 0; i < str1.size() && i < str2.size(); i++) {
            if(str1[i] != str2[i]) {
                characters[str1[i]].insert(str2[i]);
                break;
            }
        }
    }
    //DFS
    vector<pair<char, int>> order;
    for(auto a: characters) {
        bool valid = true;
        unordered_set<char> visited;
        unordered_set<char> count;
        visited.insert(a.first);
        dfs(a.first, characters, valid, visited, count);
        order.push_back(pair<char, int>(a.first, count.size()));
        if(!valid)
            return "";
    }        
    //sort
    sort(order.begin(), order.end(), [](pair<char, int> a, pair<char, int> b){
        return a.second > b.second;
    });

    //build result
    string result = "";
    for(auto a: order) {
        result += a.first;
    }
    return result;
}
void dfs(char curr, unordered_map<char, unordered_set<char>>& characters, bool& valid, unordered_set<char>& visited, unordered_set<char>& count) {
    count.insert(curr);
    if(!valid || characters[curr].empty())
        return;
    for(auto a: characters[curr]) {
        if(visited.find(a) != visited.end()) {
            valid = false;
            return;
        }
        visited.insert(a);
        dfs(a, characters, valid, visited, count);
        visited.erase(a);
    }
}