## Description

There is a new alien language which uses the latin alphabet. However, the **order** among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

**Example 1**:

Given the following words in dictionary,

1 | [ |

The correct order is: `"wertf"`

.

**Example 2:**

Given the following words in dictionary,

1 | [ |

The correct order is: `"zx"`

.

**Example 3:**

Given the following words in dictionary,

1 | [ |

The order is invalid, so return `""`

.

**Note**:

- You may assume all letters are in lowercase.
- You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
- If the order is invalid, return an empty string.
- There may be multiple valid order of letters, return any one of them is fine.

## Test cases:

### Input validations:

### Regular cases:

### COrner cases:

- zero/one word in dictionary
- assumption that not ALL letter will be ordered
- invalid order in dictionary, cycle detected
- Do I need to get ALL letter? for the adj matrix? seems not necessary. Without getting all letters, how to know if there is a cycle.

## Thoughts

Different from Course Schedule, Course Schedule II (TODO)

- total number course/nodes was unknown
- node/letter relation need to be derived from dictionary

### BFS Topological Sort

The first step of this problem is to store node relations from words in dictionary. `graph`

need to be initialized, node relationship is built, and inEdge count is also performed.

Example:

1 | dict = ['wrt', 'wcg'] |

The second step goes over nodes with zero in-edge and process the toplogical order of the graph for one of the valid alien letter order. BFS is used during the topolical sorting.

1 | public String alienOrder(String[] words) { |

### DFS Topological Sort

https://github.com/awangdev/LintCode/blob/master/Java/Alien%20Dictionary.java

## Followup

- There may be multiple valid order of letters, return the
**smallest**in lexicographical order

The follow up want one of the solutions with smallest lexicogrpahical order. We just need to replace `Queue`

with `PriorityQueue`

to make it to work.

1 | // Deque<Character> queue = new ArrayDeque<>(); |

## Summary

- find cycle in graph (DFS light weighted, BFS too much)
- directed graph
- count total number of node/construct adj matrix or list
- get one of the topological sort