难度: Hard
原题连接
内容描述
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:
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.
思路 1
参考大神seanmsha的思路
We want to build a DAG graph so that we can get a possible order that doesn't have any invalid dependencies. First we initialize all of the words with degree 0 (which means that they're the first value in sorted order). We compare every letter by adjacent words (word i and word i+1) Once we find a different letter, we know that the letter in word i+1 is greater than word i so it comes later. We add a degree to the letter in i+1 and add an entry to the letter in word i's dictionary/hashmap signifying that theres an arrow from the letter in word i to the letter in word i+1. We break the loop on the adjacent words because we already found out the reason why word i is before word i+1 (we only get information about at most 1 letter per word). Once we have our degree counts, we traverse the graph (similar to a BFS) from the nodes with degree 0. When we visit a node, we append it to the result string. We subtract one from all of the words repeatedly until all of the words have had degree 0 and have been added to the result string.
In summary:
1. Initialize all letters in words with degree 0
2. For each word i and word i+1 where i+1<n:
- If we find a letter a != letter b in word i and i+1:
- Add one to the degree and add letter b to letter a's set of letters, and go to the next word, since each word only tells us information about one pair of letters
3. Go through all of the degree== 0s and add it to the BFS queue
4. While the bfs queue is not empty:
- Pop letter a and append it to the res string
- For each letter b in letter a's set of letters:
- subtract 1 from the degree
- If it's degree is 0, add it to the queue because all it's dependencies have been added already
- Repeat 4
5. if the size of the result string != the size of the initialized letters then return an empty string(not all of the degrees hit 0 so there's a conflict)
6. Return the result string
class Solution(object):
def alienOrder(self, words):
"""
:type words: List[str]
:rtype: str
"""
maps = {}
letters = [0 for i in range(26)]
for i in range(len(words)):
for j in range(len(words[i])):
key=ord(words[i][j])-ord('a')
letters[key]=0
maps[key]=set()
for i in range(len(words)-1):
word1 = words[i]
word2 = words[i+1]
idx = 0
for j in range(min(len(word1),len(word2))):
if(word1[j]!=word2[j]):
key1 = ord(word1[j])-ord('a')
key2 = ord(word2[j])-ord('a')
count = letters[key2]
if(key2 not in maps[key1]):
letters[key2] =count+1
maps[key1].add(key2)
break
dictionary = collections.deque()
res = ''
for i in range(26):
if(letters[i]==0 and i in maps):
dictionary.appendleft(i)
while(len(dictionary)!=0):
nextup = dictionary.pop()
res+=(chr(nextup+ord('a')))
greaterSet = maps[nextup]
for greater in greaterSet:
letters[greater]-=1
if(letters[greater]==0):
dictionary.appendleft(greater)
if(len(maps)!=len(res)):
return ""
return res