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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/nine-chapter/10.-graph/269.-alien-dictionary-h.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.