269. Alien Dictionary (H)

There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language's dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language's rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Example 1:

Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"

Example 2:

Input: words = ["z","x"]
Output: "zx"

Example 3:

Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".

Constraints:

• 1 <= words.length <= 100

• 1 <= words[i].length <= 100

• words[i] consists of only lowercase English letters.

Solution:

这题主要问题是题意理解，拓扑排序可以出货。

题意理解： 啥是words按照lexicographically，这对题有啥影响。 最初的错误理解： ab, ac 可以得出 a->b, a->c 这样的关系 其实正确的理解是 ab, ac 可以得出 b->c，因为ab，ac是按照字典序排列，a和a相等，所以考虑b和c，b排在c的前面，所以 b->c

题目的关键在于想明白单词之间的关系, 相邻的两个单词之前, 我们可以忽略掉他们的共同前缀, 当碰到到两个单词中出现不相同的字母(假设这两个单词是w和w'), 那么我们就在这两个字母中间连一条边, 同时将w'的入度+1

正确顺序建立完了graph和indegree，这个题应该解决了60%。

其次，啥是输出的时候按照lexicographically，对这题有啥影响。 如果同时在indegree==0的字符里出现了 b 和 c，先输出正常字典序最小的，所以这里使用最小堆很对口。

就是当你的字典是'bd', 'ba'的情况的时候, 最后的结果有可能不是字典序的(即输出可能是"bda", 因为哈希表是没有顺序的) 为了处理这种情况, 我们在进行BFS的时候, 应该使用PrioirtyQueue来保证输出的顺序

再其次，如果输出的order和原始字符数不一样，就是说某些字符没有拓扑序，输出空。

Note: Testcase: ["abc","ab"] ,expect output: ""

Testcase: ["ab","abc"] ,expect output: "abc"

class Solution {
    public String alienOrder(String[] words) {
        
        Map<Character, Set<Character>> graph = buildGraph(words);
        if (graph == null) {
            return "";
        }
        Map<Character, Integer> indegree = getIndegree(graph);
        return topologicalSorting(graph, indegree);
    }
    
    public Map<Character, Set<Character>> buildGraph(String[] words)
    {
        Map<Character, Set<Character>> graph = new HashMap<>();
        
        // create nodes
        for(int i = 0; i< words.length; i++)
        {
            for(int j = 0; j< words[i].length(); j++)
            {
                graph.putIfAbsent(words[i].charAt(j), new HashSet<>());
            }
        }
        
        // create edges
        for(int i = 0; i< words.length-1; i++)
        {
            String word1 = words[i];
            String word2 = words[i+1];
            int index = 0;
            int minLen = Math.min(word1.length(), word2.length());
            while(index < minLen && index < minLen)
            {
                if(word1.charAt(index) != word2.charAt(index))
                {
                    graph.get(word1.charAt(index)).add(word2.charAt(index));
                    break;
                }
                index++;
            }
            
            // Testcase: ["abc","ab"] ,expect output: ""
            if(index == minLen && word1.length() > word2.length())
            {
                return null;
            }
        }
        return graph;
    }
    
    
    public Map<Character, Integer> getIndegree(Map<Character, Set<Character>> graph)
    {
        Map<Character, Integer> indegree = new HashMap<>();
        
        for(Character from : graph.keySet())
        {
            indegree.put(from, 0);
        }
        
        for(Character from : graph.keySet())
        {
            for(Character to : graph.get(from))
            {
                indegree.put(to, indegree.get(to) + 1);
            }
        }
        
        return indegree;
    }
    
    
    public String topologicalSorting(Map<Character, Set<Character>> graph, Map<Character, Integer> indegree)
    {
        // as we should return the topo order with lexicographical order
        // we should use PriorityQueue instead of a FIFO Queue
        StringBuilder sb = new StringBuilder();
        Queue<Character> queue = new PriorityQueue<>();
        for(Character c : indegree.keySet())
        {
            if(indegree.get(c) == 0)
            {
                queue.offer(c);
            }
        }
        
        while(!queue.isEmpty())
        {
            Character current = queue.poll();
            sb.append(current);
            for(Character adj : graph.get(current))
            {
                indegree.put(adj, indegree.get(adj)-1);
                if(indegree.get(adj) == 0)
                {
                    queue.offer(adj);
                }
            }
        }
        
        //最后还要判断排出来的拓扑序是不是有效的, 是不是所有的节点都遍历过了
        //如果不是的话我们直接输出空串, 证明组成给定的这些单词的字母没有办法组成一个合理的拓扑序
        if(sb.length() != indegree.size())
        {
            return "";
        }
        return sb.toString();
    }
}