> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0269-alien-dictionary.md).

# 0269. Alien Dictionary

<https://leetcode.com/problems/alien-dictionary>

## Description

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.

## ac

1. How to intepret as a topological problem?
2. How to build the graph?

```java
class Solution {
    public String alienOrder(String[] words) {
        // edge cases
        if (words == null || words.length == 0)
            return "";

        // map is more robust than array
        Map<Character, Integer> inde = new HashMap<Character, Integer>();
        Map<Character, Set<Character>> g = new HashMap<Character, Set<Character>>();

        // get chars
        for (String w : words) {
            for (int i = 0; i < w.length(); i++) {
                char c = w.charAt(i);
                inde.put(c, 1);
                if(!g.containsKey(c)) g.put(c, new HashSet<Character>());
            }
        }

        // build graph, get indegree
        for (int i = 0; i < words.length - 1; i++) {
            char[] f = words[i].toCharArray();
            char[] s = words[i+1].toCharArray();
            int len = Math.min(f.length, s.length);

            for (int j = 0; j < len; j++) {
                if (f[j] == s[j]) continue;
                if (g.get(f[j]).add(s[j])) { // ignore duplicate edge
                    inde.put(s[j], inde.get(s[j]) + 1);
                }
                break;
            }
        }

        // BFS
        StringBuilder res = new StringBuilder();
        Queue<Character> q = new LinkedList<Character>();
        for (char c : inde.keySet()){
            if (inde.get(c) == 1) q.offer(c);
        }
        while (!q.isEmpty()) {
            char c = q.poll();
            res.append(c);
            for (char next : g.get(c)) {
                inde.put(next, inde.get(next) - 1);
                if (inde.get(next) == 1) q.offer(next);
            }
        }

        // validate
        if (res.length() != inde.size()) {
            return "";
        } else {
            return res.toString();
        }
    }
}
/*
build a graph
indegree
BFS
*/
```