Alien Dictionary

• Lintcode : 892 / Leetcode : 269
• Level : Hard

Problem

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
Example 1:

Input：["wrt","wrf","er","ett","rftt"]
Output："wertf"
Explanation：
from "wrt"and"wrf" ,we can get 't'<'f'
from "wrt"and"er" ,we can get 'w'<'e'
from "er"and"ett" ,we can get 'r'<'t'
from "ett"and"rftt" ,we can get 'e'<'r'
So return "wertf"

Example 2:

Input：["z","x"]
Output："zx"
Explanation：
from "z" and "x"，we can get 'z' < 'x'
So return "zx"
Notice
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 the smallest in normal lexicographical order

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(string numbers * the index of avg different char position)
space: O(n)

Answer

/*
1. 利用suc存某字符的全部後缀，利用pre存某字符的全部前缀，chars存全部出現的字符。
2. 在建前缀和後缀map的過程中，s存上一個字串，t存當前字串，模擬字典序比较，按位比较，不相同说明當前字元是上個字串對應位置字元的後缀
3. head存拓樸排序當前的起点（即入度为0的字元，沒有前綴的意思），故首先遍歷pre，因為p.first一定有前缀，不能作起點，先從head中清除。
4. 每次取出head的頭部，即起點，加入答案中，然後清除，遍歷後缀，找連接起點的字元，刪除前綴，如果刪除後字元前缀為空，也可以成為起點，加入head。
*/
class Solution {
public:
    string alienOrder(vector<string> &words) {
        map<char, set<char>> suc, pre;
        set<char> chars;
        string s;
        for (string t : words) {
            chars.insert(t.begin(), t.end());
            for (int i = 0; i < min(t.size(), s.size()); i++) {
                char a = s[i], b = t[i];
                if (a != b) {
                    pre[b].insert(a);
                    suc[a].insert(b);
                    break;
                }
            }
            s = t;
        }

        set<char> head = chars;
        for (auto p : pre)
            head.erase(p.first);
        string order;
        while (head.size()) {
            auto it = head.begin();
            char c = *it;
            head.erase(c);
            order += c;
            for (auto i : suc[c]) {
                pre[i].erase(c);
                if (pre[i].empty()) {
                    head.insert(i);
                }
            }
        }
        // return order; -> false
        return order.size() == chars.size() ? order : "";
    }
};

tags: BFS

​