lintcode-892 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.

1
2
3
4
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 **the smallest in normal lexicographical order**

Example:

1
2
3
4
5
6
7
8
Input：["wrt","wrf","er","ett","rftt"]
Output："wertf"
Explanation：
from "wrt"and"wrf" ,we can get 't'<'f'
from "wrt"and"er" ,we can get 'w'<'e'
from "er"and"ett" ,we can get 'r'<'t'
from "ett"and"rtff" ,we can get 'e'<'r'
So return "wertf"

思路

典型拓扑排序. 因为返回可能的结果中字典序最小的, 在建立res数组时, 队列的pop顺序要从小到大. 所以队列用pq(heap).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import heapq
class Solution:
    """
    @param words: a list of words
    @return: a string which is correct order
    """
    def alienOrder(self, words):
        # Write your code here
        g = collections.defaultdict(set)
        ind = collections.defaultdict(int)
        
        for i in xrange(1, len(words)):
            for j in xrange(min(len(words[i-1]), len(words[i]))):
                if words[i-1][j] != words[i][j]:
                    g[words[i-1][j]].add(words[i][j])
                    ind[words[i][j]] += 1
                    break
        hp = []
        res = []
        char_set = set("".join(w for w in words))
        for c in char_set:
            if ind[c] == 0:
                heapq.heappush(hp, c)
        
        while hp:
            cur = heapq.heappop(hp)
            res.append(cur)
            for nei in g[cur]:
                ind[nei] -= 1
                if ind[nei] == 0:
                    heapq.heappush(hp, nei)
                    
        return "".join(res) if len(res) == len(char_set) else ""