LeetCode 269 / LintCode 892 Alien Dictionary

思路

【lintcode 892有一个条件不一样：遇到有多个顺序的时候，输出最小的那个】
思路：拓扑排序。每个字母都是图中的一个节点，然后通过比较相邻的两个字符串得到具体两个字母的顺序【由于传递性，所以只需要比较相邻两个字符串】。可以使用优先队列来做拓扑排序，这样可以保证取到的顺序一直是最小的。

时间复杂度O(naL+2mlogm), n-字符串个数，aL-单词平均长度，m-总字母个数。因为在topoSort中每个字母最坏情况下都是入队和出队各一次，因此为2m*logm

空间复杂度O(m^2)

代码

class Solution {
    public String alienOrder(String[] words) {
    Map<Character, Set<Character>> graph = buildGraph(words);return topoSort(graph);}private Map<Character, Set<Character>> buildGraph(String[] words) {
    Map<Character, Set<Character>> graph = new HashMap<>();// create nodesfor (int i = 0; i < words.length; i++) {
    for (int j = 0; j < words[i].length(); j++) {
    char c = words[i].charAt(j);if (!graph.containsKey(c)) {
    graph.put(c, new HashSet<>());}}}// create edgesfor (int i = 0; i < words.length - 1; i++) {
    int index = 0;while (index < words[i].length() && index < words[i + 1].length()) {
    if (words[i].charAt(index) != words[i + 1].charAt(index)) {
    graph.get(words[i].charAt(index)).add(words[i + 1].charAt(index));break;}index++;}}return graph;}private Map<Character, Integer> getIndegree(Map<Character, Set<Character>> graph) {
    Map<Character, Integer> indegree = new HashMap<>();for (char c : graph.keySet()) {
    indegree.put(c, 0);}for (char c : graph.keySet()) {
    for (char v : graph.get(c)) {
    indegree.put(v, indegree.get(v) + 1);}}return indegree;}private String topoSort(Map<Character, Set<Character>> graph) {
    Map<Character, Integer> indegree = getIndegree(graph);Queue<Character> queue = new PriorityQueue<>();for (char c : indegree.keySet()) {
    if (indegree.get(c) == 0) {
    queue.offer(c);}}StringBuilder sb = new StringBuilder();while (!queue.isEmpty()) {
    char c = queue.poll();sb.append(c);for (char next : graph.get(c)) {
    int nextDegree = indegree.get(next) - 1;indegree.put(next, nextDegree);if (nextDegree == 0) {
    queue.offer(next);}}}if (sb.length() != indegree.size()) {
    return "";}return sb.toString();}
}