# 269. Alien Dictionary

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:

```Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]

Output: `"wertf"`
```

Example 2:

```Input:
[
"z",
"x"
]

Output: `"zx"`
```

Example 3:

```Input:
[
"z",
"x",
"z"
]

Output: `""`

Explanation: The order is invalid, so return `""`.
```

Note:

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

```class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
# 可能有环， 每个单词只有一个字符的情况, 不符合字典序的情况，['err', 'e']
graph = collections.defaultdict(set)
nodes = set()
nodes.update(words)
for i in xrange(1, len(words)):
diff = 0
for j in xrange(min(len(words[i-1]), len(words[i]))):
if words[i-1][j] != words[i][j]:
diff += 1
break
if diff == 0 and len(words[i-1]) > len(words[i]):
return ""
nodes.update(words[i])

hashmap = collections.defaultdict(int)
for node in nodes:
for n in graph[node]:
hashmap[n] += 1

queue = collections.deque()
for node in graph:
if node not in hashmap:
queue.append(node)
res = []
while queue:
node = queue.popleft()
res.append(node)
for n in graph[node]:
hashmap[n] -= 1
if hashmap[n] == 0:
queue.append(n)         #判断是否有环
if len(res) != len(nodes):
res = []
return "".join(res)    ```

THE END  