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.

给一个单词字典，单词是按照字典序排序，求字母的排序。以题中例子，先看所有单词的第1个字符，可知顺序是w->e-r。然后对于两个连续的单词，找到第一个不相同的字符，比如 wrt和wrf，wr之后t在f之前，所以排序是 t->f。按照当前字母前面出现的字母个数排序，比如w前面有0个字母，e前面有w一个字母，r前面有e和w两个字母，所以排序是w->e->r。因此可以归结为一个拓扑问题，先建图，然后进行遍历。首先统计入度：w的入度是0，e的入度是1，r的入度是2。先把入度为0的节点放入结果中，然后取出w后面连接的节点，将他们的入度-1，如果有入度为0的节点，再放入结果中。

time: 建图->O(n*k), Topological sort-> O(26 + n) = O(n)，space: O(n)，主要是Map的大小，k表示单词平均长度。

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。拓扑排序通常用来“排序”具有依赖关系的任务。

该序列必须满足下面两个条件：1）每个顶点出现且只出现一次。2）若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

如何写出它的拓扑排序呢？这里说一种比较常用的方法：

  1. 从 DAG 图中选择一个没有前驱（即入度为0）的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

参考：拓扑排序（Topological Sorting）

Java：

public class Solution {

    public String alienOrder(String[] words) {   // Topological sorting - Kahn's Algorithm

        if(words == null || words.length == 0) {

            return "";

        }

        Map<Character, Set<Character>> graph = new HashMap<>();

        Set<Character> set = new HashSet<>();

        for (String word : words) {

            for (int i = 0; i < word.length(); i++) {

                set.add(word.charAt(i));

            }

        }

        int[] inDegree = new int[26];

        for (int k = 1; k < words.length; k++) {

            String preStr = words[k - 1];

            String curStr = words[k];

            for (int i = 0; i < Math.min(preStr.length(), curStr.length()); i++) {

                char preChar = preStr.charAt(i);

                char curChar = curStr.charAt(i);

                if (preChar != curChar) {

                    if (!graph.containsKey(preChar)) {

                        graph.put(preChar, new HashSet<Character>());

                    }

                    if (!graph.get(preChar).contains(curChar)) {

                        inDegree[curChar - 'a']++;

                    }

                    graph.get(preChar).add(curChar);

                    break;

                }

            }

        }

        Queue<Character> queue = new LinkedList<>();

        for (int i = 0; i < inDegree.length; i++) {

            if (inDegree[i] == 0) {

                char c = (char)('a' + i);

                if (set.contains(c)) {

                    queue.offer(c);

                }

            }

        }

        StringBuilder sb = new StringBuilder();

        while (!queue.isEmpty()) {

            char c = queue.poll();

            sb.append(c);

            if (graph.containsKey(c)) {

                for (char l : graph.get(c)) {

                    inDegree[l - 'a']--;

                    if (inDegree[l - 'a'] == 0) {

                        queue.offer(l);

                    }

                }

            }

        }

        return sb.length() != set.size() ? "" : sb.toString();

    }

}

Python：BFS

class Solution(object):

    def alienOrder(self, words):

        """

        :type words: List[str]

        :rtype: str

        """

        result, zero_in_degree_queue, in_degree, out_degree = [], collections.deque(), {}, {}

        nodes = sets.Set()

        for word in words:

            for c in word:

                nodes.add(c)

        for i in xrange(1, len(words)):

            if len(words[i-1]) > len(words[i]) and \

                words[i-1][:len(words[i])] == words[i]:

                    return ""

            self.findEdges(words[i - 1], words[i], in_degree, out_degree)

        for node in nodes:

            if node not in in_degree:

                zero_in_degree_queue.append(node)

        while zero_in_degree_queue:

            precedence = zero_in_degree_queue.popleft()

            result.append(precedence)

            if precedence in out_degree:

                for c in out_degree[precedence]:

                    in_degree[c].discard(precedence)

                    if not in_degree[c]:

                        zero_in_degree_queue.append(c)

                del out_degree[precedence]

        if out_degree:

            return ""

        return "".join(result)

    # Construct the graph.

    def findEdges(self, word1, word2, in_degree, out_degree):

        str_len = min(len(word1), len(word2))

        for i in xrange(str_len):

            if word1[i] != word2[i]:

                if word2[i] not in in_degree:

                    in_degree[word2[i]] = sets.Set()

                if word1[i] not in out_degree:

                    out_degree[word1[i]] = sets.Set()

                in_degree[word2[i]].add(word1[i])

                out_degree[word1[i]].add(word2[i])

                break　　

Python：DFS　　

class Solution2(object):

    def alienOrder(self, words):

        # Find ancestors of each node by DFS.

        nodes, ancestors = sets.Set(), {}

        for i in xrange(len(words)):

            for c in words[i]:

                nodes.add(c)

        for node in nodes:

            ancestors[node] = []

        for i in xrange(1, len(words)):

            if len(words[i-1]) > len(words[i]) and \

                words[i-1][:len(words[i])] == words[i]:

                    return ""

            self.findEdges(words[i - 1], words[i], ancestors)

        # Output topological order by DFS.

        result = []

        visited = {}

        for node in nodes:

            if self.topSortDFS(node, node, ancestors, visited, result):

                return ""

        return "".join(result)

    # Construct the graph.

    def findEdges(self, word1, word2, ancestors):

        min_len = min(len(word1), len(word2))

        for i in xrange(min_len):

            if word1[i] != word2[i]:

                ancestors[word2[i]].append(word1[i])

                break

    # Topological sort, return whether there is a cycle.

    def topSortDFS(self, root, node, ancestors, visited, result):

        if node not in visited:

            visited[node] = root

            for ancestor in ancestors[node]:

                if self.topSortDFS(root, ancestor, ancestors, visited, result):

                    return True

            result.append(node)

        elif visited[node] == root:

            # Visited from the same root in the DFS path.

            # So it is cyclic.

            return True

        return False

C++：

class Solution {

public:

    string alienOrder(vector<string>& words) {

        if(words.size() == 0)

            return "";

        unordered_map<char, vector<char>> d;

        unordered_map<char, bool> used;

        for(auto s : words) {

            for(int i = 0; i < s.length(); i++) {

                if(used.find(s[i]) == used.end())

                    used.insert(pair<char, bool>(s[i], false));

            }

        }

        for(int i = 1; i < words.size(); i++) {

            string cur = words[i];

            string pre = words[i - 1];

            int j = 0;

            while(j < min(cur.length(), pre.length())) {

                if(cur[j] != pre[j]) {

                    if(d.find(pre[j]) == d.end()) {

                        vector<char> list;

                        list.push_back(cur[j]);

                        d.insert(pair<char, vector<char>>(pre[j], list));

                    }

                    else {

                        d[pre[j]].push_back(cur[j]);

                    }

                    break;

                }

                j++;

            }

        }

        string result = "";

        for(auto it = d.begin(); it != d.end(); it++) {

            if(!used[it->first]) {

                unordered_set<char> loop;

                bool l = topologicalSort(d, used, result, it->first, loop);

                if(l)

                    return "";

            }

        }

        for(auto i = used.begin(); i != used.end(); i++) {

            if(!i->second)

                result = i->first + result;

        }

        return result;

    }

    bool topologicalSort(unordered_map<char, vector<char>> d, unordered_map<char, bool>& used, string& result, char cur, unordered_set<char>& loop) {

        used[cur] = true;

        loop.insert(cur);

        for(auto i : d[cur]) {

            if(loop.find(i) != loop.end())

                return true;

            if(!used[i]) {

                bool l = topologicalSort(d, used, result, i, loop);

                if(l)

                    return true;

            }

        }

        result = cur + result;

        return false;

    }

};　

　　　

类似题目：

[LeetCode] 207. Course Schedule 课程安排

[LeetCode] 210. Course Schedule II 课程安排II

All LeetCode Questions List 题目汇总

最新文章

  1. python征程3.0（python对象）
  2. Android Fragment (一)
  3. HTML5 CSS3学习
  4. 使用beanUtils操纵javabean
  5. JS中的事件冒泡（Bubble）和事件捕获（capture）以及如何阻止事件的冒泡
  6. Python顺序集合之 tuple
  7. ORACLE触发器概述之【行触发器】【weber出品】
  8. UP UP UP!(dp)
  9. C#基础：事件（一） 【转】
  10. Android KeyLogger Demo
  11. 聚类之dbscan算法
  12. 【Python】 文件目录比较工具filecmp和difflib
  13. Linux内核入门到放弃-虚拟文件系统-《深入Linux内核架构》笔记
  14. JVM思考-init和clinit区别
  15. Linux学习之常用文件处理命令(一)
  16. Python中fileinput模块使用方法
  17. Why Linux Doesn’t Need Defragmenting
  18. .NetCore利用Swagger生成 XML文档需要注意生成路径的地址
  19. url参数带点
  20. Objective-C-代码块Block回顾

热门文章

  1. keras中to_categorical()函数解析
  2. 09-Flutter移动电商实战-移动商城数据请求实战
  3. jeecg uedit 自定义图片上传路径
  4. LeetCode 1027. Longest Arithmetic Sequence
  5. 实训作业6 （数据I/O）
  6. Web 项目的文件/文件夹上传下载
  7. Omnibus-ctl: What is it and what can it do for you?
  8. 学生管理系统(Nodejs)
  9. something about 乘法逆元
  10. TCP BBR 从开启到关闭：以 Debian 9 为例