> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/10.-graph/269.-alien-dictionary-h.md).

# 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`.

&#x20;

**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 "".
```

&#x20;

**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'](https://www.jiuzhang.com/problem/alien-dictionary/)的情况的时候, 最后的结果有可能不是字典序的(即输出可能是"bda", 因为哈希表是没有顺序的) 为了处理这种情况, 我们在进行BFS的时候, 应该使用**PrioirtyQueue来保证输出的顺序**

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

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

&#x20;         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();
    }
}
```