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.
- code post order dfs, java
class Solution {
private StringBuilder res = new StringBuilder();
private Map<Character, ArrayList<Character>> preDic = new HashMap();
private Map<Character, Boolean> seen = new HashMap();
public String alienOrder(String[] words) {
// initailse predic
for (String word: words){
for (Character c: word.toCharArray()){
preDic.putIfAbsent(c, new ArrayList());
}
}
// build pre dic, dfs
for (int i = 1; i < words.length; ++i){
String first = words[i-1];
String second = words[i];
// abc ab
if (first.startsWith(second) && first.length() > second.length()){
return "";
}
int j = 0;
while (j < Math.min(first.length(), second.length())){
if (first.charAt(j) != second.charAt(j)){
preDic.get(second.charAt(j)).add(first.charAt(j));
break;
}
j++;
}
}
for (Character c: preDic.keySet()){
if(!dfs(c)) return "";
}
return res.toString();
}
public boolean dfs(Character c){
if (seen.containsKey(c)){
return seen.get(c);
}
seen.put(c, false);
for (Character pre: preDic.get(c)){
boolean noCycle = dfs(pre);
if (!noCycle){
return false;
}
}
seen.put(c, true);
res.append(c);
return true;
}
}
- code post order dfs pythonM
class Solution:
def alienOrder(self, words: List[str]) -> str:
# Step 0: Put all unique letters into the adj list.
reverse_adj_list = {c : [] for word in words for c in word}
# Step 1: Find all edges and put them in reverse_adj_list.
for first_word, second_word in zip(words, words[1:]):
for c, d in zip(first_word, second_word):
if c != d:
reverse_adj_list[d].append(c)
break
else: # Check that second word isn't a prefix of first word.
if len(second_word) < len(first_word):
return ""
# Step 2: Depth-first search.
seen = {} # False = grey, True = black.
output = []
def visit(node): # Return True iff there are no cycles.
if node in seen:
return seen[node] # If this node was grey (False), a cycle was detected.
seen[node] = False # Mark node as grey.
for next_node in reverse_adj_list[node]:
result = visit(next_node)
if not result:
return False # Cycle was detected lower down.
seen[node] = True # Mark node as black.
output.append(node)
return True
if not all(visit(node) for node in reverse_adj_list):
return ""
return "".join(output)
-code with indegree, topological sorting
class Solution:
def alienOrder(self, words: List[str]) -> str:
order_dic = defaultdict(list)
indegree = {c:0 for word in words for c in word}
for i in range(1, len(words)):
pre, nex = words[i-1], words[i] # compare only two, not with all rest, becuase a>b and b>c, sure a>c
for j in range(min(len(pre), len(nex))):
if pre[j] != nex[j]:
if nex[j] not in order_dic[pre[j]]:
order_dic[pre[j]].append(nex[j])
indegree[nex[j]] += 1
break
else: # only execute when not break
if len(pre) > len(nex): # abc > ab
return ""
s = [c for c in indegree if indegree[c] == 0]
res = []
while s:
cur = s.pop()
res.append(cur)
for nex in order_dic[cur]:
indegree[nex] -= 1
if indegree[nex] == 0:
s.append(nex)
return "".join(res) if len(res) == len(indegree) else ""