> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/topological_sortff0c_tuo_pu_pai_xu/alien_dictionary.md).

# Alien Dictionary

## [Alien Dictionary](https://leetcode.com/problems/alien-dictionary/)

先说一个自己写这题时犯的错误，就是建 class 的时候没直接建 Node ，而是建了个 Edge，再用 Edge 去建 ArrayList\[] 代表 Graph，太麻烦了，只是在故意贴近之前写题的模板而已，因为那几题给的都是 edges.

### 要自己从头建 Graph ，就应该直接从 Node 写起，记 state, children, indegree 都方便。

### 题意解析：

> * 同一个单词中的字母先后顺序没有任何意义；
> * 相邻单词之间，按照 Lexicographical order 排列的意义是，双方字符串中第一个不 match 的字符代表这一条 directed edge，即字符的先后顺序；
> * 如果所有字符一致，但是其中一个单词长一些，也无法学习到 edge，**但是多出来的那个字符要记得加入字典**，暂时作为一个独立 node;
> * 如果发现字典 Graph 中有环，返回空字符串；
> * 如果字典中只有一个单词，返回此单词的任意顺序皆可；
> * 加入新 edge 的时候，记得判重，不要加入重复 child 节点；

超过 69% 的 DFS 写法：

```java
public class Solution {
    private class Node{
        int chrInt;
        int state;
        int indegree;
        ArrayList<Integer> children;
        public Node(int chrInt){
            this.chrInt = chrInt;
            state = 0;
            indegree = 0;
            children = new ArrayList<Integer>();
        }
        public char getChar(){
            return (char) (this.chrInt + 'a');
        }
    }

    public String alienOrder(String[] words) {
        HashMap<Integer, Node> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        if(words.length == 1) return words[0];

        for(int i = 0; i < words.length - 1; i++){
            learn(words[i], words[i + 1], map);
        }

        for(int i : map.keySet()){
            if(map.get(i).state == 0 && dfs(i, sb, map)) return "";
        }

        return sb.reverse().toString();
    }

    private boolean dfs(int cur, StringBuilder sb, HashMap<Integer, Node> map) {

        Node node = map.get(cur);

        node.state = 1;
        boolean hasCycle = false;

        for(int i = 0; i < node.children.size(); i++){
            int next = node.children.get(i);
            if(map.get(next).state == 1) hasCycle = true;
            else if (map.get(next).state == 0) {
                hasCycle = hasCycle || dfs(next, sb, map);
            }
        }

        node.state = 2;
        sb.append(node.getChar());

        return hasCycle;
    }

    private void learn(String word1, String word2, HashMap<Integer, Node> map){
        int ptr1 = 0;
        int ptr2 = 0;

        while(ptr1 < word1.length() && ptr2 < word2.length()){
            int parent = word1.charAt(ptr1++) - 'a';
            int child = word2.charAt(ptr2++) - 'a';

            if(!map.containsKey(parent)) map.put(parent, new Node(parent));
            if(!map.containsKey(child)) map.put(child, new Node(child));

            if(parent != child){
                Node p = map.get(parent);
                Node c = map.get(child);

                if(!p.children.contains(child)){
                    p.children.add(child);
                    c.indegree ++;
                }
                break;
            }
        }
        while(ptr1 < word1.length()){
            int node = word1.charAt(ptr1++) - 'a';
            if(!map.containsKey(node)) map.put(node, new Node(node));
        }
        while(ptr2 < word2.length()){
            int node = word2.charAt(ptr2++) - 'a';
            if(!map.containsKey(node)) map.put(node, new Node(node));
        }
    }
}
```

### 同样的结构， BFS 写法：

```java
public class Solution {
    private class Node{
        int chrInt;
        int state;
        int indegree;
        ArrayList<Integer> children;
        public Node(int chrInt){
            this.chrInt = chrInt;
            state = 0;
            indegree = 0;
            children = new ArrayList<Integer>();
        }
        public char getChar(){
            return (char) (this.chrInt + 'a');
        }
    }

    public String alienOrder(String[] words) {
        HashMap<Integer, Node> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        if(words.length == 1) return words[0];

        for(int i = 0; i < words.length - 1; i++){
            learn(words[i], words[i + 1], map);
        }

        Queue<Node> queue = new LinkedList<>();
        int total = 0;
        for(int i : map.keySet()){
            total++;
            if(map.get(i).indegree == 0) queue.offer(map.get(i));
        }

        int count = 0;
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            sb.append(cur.getChar());
            count ++;

            for(int next : cur.children){
                Node child = map.get(next);
                child.indegree--;
                if(child.indegree == 0) queue.offer(child);
            }
        }

        return (count == total) ? sb.toString() : "" ;
    }


    private void learn(String word1, String word2, HashMap<Integer, Node> map){
        int ptr1 = 0;
        int ptr2 = 0;

        while(ptr1 < word1.length() && ptr2 < word2.length()){
            int parent = word1.charAt(ptr1++) - 'a';
            int child = word2.charAt(ptr2++) - 'a';

            if(!map.containsKey(parent)) map.put(parent, new Node(parent));
            if(!map.containsKey(child)) map.put(child, new Node(child));

            if(parent != child){
                Node p = map.get(parent);
                Node c = map.get(child);

                if(!p.children.contains(child)){
                    p.children.add(child);
                    c.indegree ++;
                }
                break;
            }
        }
        while(ptr1 < word1.length()){
            int node = word1.charAt(ptr1++) - 'a';
            if(!map.containsKey(node)) map.put(node, new Node(node));
        }
        while(ptr2 < word2.length()){
            int node = word2.charAt(ptr2++) - 'a';
            if(!map.containsKey(node)) map.put(node, new Node(node));
        }
    }
}
```

### 不建 Node class 而用 HashMap 的做法如下：

### 自己在写这题白板的时候犯了一个小错误，就是一旦发现了 char1 != char2 ，处理完了要记得 break，不要乱学新的 edge 出来。

```java
    public String alienOrder(String[] words) {
        HashMap<Character, Set<Character>> graphMap = new HashMap<>();
        HashMap<Character, Integer> indegreeMap = new HashMap<>();

        for(String str : words){
            for(int i = 0; i < str.length(); i++){
                indegreeMap.put(str.charAt(i), 0);
                graphMap.put(str.charAt(i), new HashSet<>());
            }
        }

        for(int i = 0; i < words.length - 1; i++){
            String word1 = words[i];
            String word2 = words[i + 1];

            for(int index = 0; index < Math.min(word1.length(), 
                                                word2.length()); index++){
                char char1 = word1.charAt(index);
                char char2 = word2.charAt(index);
                if(char1 != char2){
                    Set<Character> neighbours = graphMap.get(char1);
                    if(!neighbours.contains(char2)){
                        int indegree = indegreeMap.get(char2);
                        indegreeMap.put(char2, indegree + 1);
                    }
                    graphMap.get(char1).add(char2);
                    break;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        Queue<Character> queue = new LinkedList<>();
        for(Character chr : indegreeMap.keySet()){
            if(indegreeMap.get(chr) == 0) queue.offer(chr);
        }
        int count = 0;
        while(!queue.isEmpty()){
            char curChar = queue.poll();
            count ++;
            sb.append(curChar);

            for(Character child : graphMap.get(curChar)){
                int degree = indegreeMap.get(child);
                degree --;
                indegreeMap.put(child, degree);
                if(degree == 0) queue.offer(child);
            }
        }

        return (count == graphMap.keySet().size()) ? sb.toString(): "";
    }
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://mnunknown.gitbook.io/algorithm-notes/topological_sortff0c_tuo_pu_pai_xu/alien_dictionary.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.