- Alien Dictionary
https://leetcode-cn.com/problems/alien-dictionary/
困难
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.
相关企业
- Facebook|16
- 爱彼迎 Airbnb|16
- 亚马逊 Amazon|10
- 谷歌 Google|7
- 彭博 Bloomberg|4
相关标签
- Depth-First Search
- Breadth-First Search
- Graph
- Topological Sort
- Array
- String
相似题目
- Course Schedule II 中等
python
class Solution:
def alienOrder(self, words: List[str]) -> str:
if not words:
return ""
letter2NextLettersGraph, letter2IndegreeMap = self.buildNextLettersGraphAndIndegreeMap(words)
if not letter2NextLettersGraph:
return ""
print(letter2IndegreeMap, letter2NextLettersGraph)
# bfs:
# use heapq instead of regular queue so that we can get the
# smallest alien lexicographical order
queue = [letter for letter in letter2IndegreeMap if letter2IndegreeMap[letter] == 0]
heapify(queue)
topoorder = []
while queue:
currletter = heappop(queue)
topoorder.append(currletter)
for nextletter in letter2NextLettersGraph[currletter]:
letter2IndegreeMap[nextletter] -= 1
if letter2IndegreeMap[nextletter] == 0:
heappush(queue, nextletter)
if len(topoorder) == len(letter2NextLettersGraph):
return ''.join(topoorder)
return ""
def buildNextLettersGraphAndIndegreeMap(self, words):
letter2NextLettersGraph = {}
letter2IndegreeMap = {}
for word in words:
for letter in word:
letter2NextLettersGraph[letter] = set()
letter2IndegreeMap[letter] = 0
for i in range(len(words) - 1):
length = min(len(words[i]), len(words[i+1]))
for j in range(length):
if words[i][j] != words[i+1][j]:
letter2NextLettersGraph[words[i][j]].add(words[i+1][j])
break
if j == length - 1:
if len(words[i]) > len(words[i + 1]):
return None, None
for letter in letter2NextLettersGraph:
for nextletter in letter2NextLettersGraph[letter]:
letter2IndegreeMap[nextletter] += 1
return letter2NextLettersGraph, letter2IndegreeMapjava
class Solution {
private Map<Character, Set<Character>> letter2NextLettersGraph;
private Map<Character, Integer> letter2IndegreeMap;
public String alienOrder(String[] words) {
this.letter2NextLettersGraph = this.buildLetter2NextLettersGraph(words);
if (this.letter2NextLettersGraph == null || this.letter2NextLettersGraph.size() == 0){
return "";
}
this.letter2IndegreeMap = this.buildLetter2IndegreeMap(words);
// System.out.println(this.letter2NextLettersGraph);
// System.out.println(this.letter2IndegreeMap);
// bfs
Queue<Character> queue = new PriorityQueue<Character>();
StringBuilder topoOrderResult = new StringBuilder();
// start nodes
for (Character letter: this.letter2IndegreeMap.keySet()){
if (this.letter2IndegreeMap.get(letter) == 0){
queue.offer(letter);
}
}
// bfs
while (!queue.isEmpty()){
Character currLetter = queue.poll();
topoOrderResult.append(currLetter);
for (Character nextLetter: this.letter2NextLettersGraph.get(currLetter)){
this.letter2IndegreeMap.put(nextLetter, this.letter2IndegreeMap.get(nextLetter) - 1);
if (this.letter2IndegreeMap.get(nextLetter) == 0){
queue.offer(nextLetter);
}
}
}
if (topoOrderResult.length() == this.letter2NextLettersGraph.size()){
return topoOrderResult.toString();
}
return "";
}
public Map<Character, Set<Character>> buildLetter2NextLettersGraph(String[] words){
Map<Character, Set<Character>> letter2NextLettersGraph = new HashMap<>();
for (String word: words){
for (int i = 0; i < word.length(); i++){
Character letter = word.charAt(i);
if (!letter2NextLettersGraph.containsKey(letter)){
letter2NextLettersGraph.put(letter, new HashSet<Character>());
}
}
}
for (int i = 0; i < words.length - 1; i++){
int shorterLength = Math.min(words[i].length(), words[i + 1].length());
for (int j = 0; j < shorterLength; j++){
Character currLetter = words[i].charAt(j);
Character nextLetter = words[i + 1].charAt(j);
if (currLetter != nextLetter){
letter2NextLettersGraph.get(currLetter).add(nextLetter);
break;
}
if (j == shorterLength - 1){
if (words[i].length() > words[i + 1].length()){
return null;
}
}
}
}
return letter2NextLettersGraph;
}
public Map<Character, Integer> buildLetter2IndegreeMap(String[] words){
this.letter2IndegreeMap = new HashMap<>();
for (Character letter: this.letter2NextLettersGraph.keySet() ){
if (!this.letter2IndegreeMap.containsKey(letter)){
this.letter2IndegreeMap.put(letter, 0);
}
}
for (Character letter: this.letter2NextLettersGraph.keySet() ){
for (Character nextLetter: this.letter2NextLettersGraph.get(letter)){
if (this.letter2IndegreeMap.containsKey(nextLetter)){
this.letter2IndegreeMap.put(nextLetter, this.letter2IndegreeMap.get(nextLetter) + 1);
}
}
}
return this.letter2IndegreeMap;
}
}