269.Alien-Dictionary

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:
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.

代码

Approach #1 Topology Traversal + BFS

class Solution {
public String alienOrder(String[] words) {
if (words == null || words.length == 0) return "";
Map<Character, Set<Character>> map = new HashMap<>();
Map<Character, Integer> degree = new HashMap<>();
for (String s: words){
for (char c: s.toCharArray()) {
map.putIfAbsent(c, new HashSet());
degree.putIfAbsent(c, 0);
}
}
for (int i = 0; i < words.length - 1; i++) {
String cur = words[i];
String next = words[i + 1];
for (int j = 0; j < Math.min(cur.length(), next.length()); j++) {
char c1 = cur.charAt(j);
char c2 = next.charAt(j);
if (c1 != c2) {
Set<Character> set = map.get(c1);
if (!set.contains(c2)) { // ESSENTIAL!!
set.add(c2);
map.put(c1, set);
degree.put(c2, degree.get(c2) + 1);
}
break;
}
}
}
// BFS
Queue<Character> q = new LinkedList<Character>();
for (char c : degree.keySet()) {
if (degree.get(c) == 0) {
q.add(c);
}
}
StringBuffer sb = new StringBuffer();
while (!q.isEmpty()) {
char c = q.poll();
sb.append(c);
if (map.containsKey(c)) {
for (char c2 : map.get(c)) {
degree.put(c2, degree.get(c2) - 1);
if (degree.get(c2) == 0) {
q.offer(c2);
}
}
}
}
if (sb.length() != degree.size()) return "";
return sb.toString();
}
}

Approach #2 DFS

DFS, mark visited. When dfs down to an leaf element, it'll be the last element of the final output. (reverse order)
class Solution {
Map<Character, List<Character>> map = new HashMap<>();
Map<Character,Integer> visited = new HashMap<>();
StringBuffer sb = new StringBuffer();
public String alienOrder(String[] words) {
if (words == null || words.length == 0) return "";
// build graph, and visited map
buildGraph(words);
// Topological sort with dfs
for (char c : map.keySet()) {
if (!dfs(c)) {
return "";
}
}
return sb.toString();
}
private void buildGraph(String[] words) {
for (String word : words) {
for (char c : word.toCharArray()) {
if (!map.containsKey(c)) {
map.put(c, new ArrayList<>());
visited.put(c, 0);
}
}
}
for (int i = 0; i < words.length - 1; i++) {
int index = 0;
while (index < words[i].length() && index < words[i + 1].length()) {
char c1 = words[i].charAt(index);
char c2 = words[i + 1].charAt(index);
if (c1 != c2) {
map.get(c1).add(c2);
break;
}
index++;
}
}
}
// Traverse all the way to the leaves in topological order
private boolean dfs(Character c) {
if (visited.get(c) == 1) return true; // can reach the leaves
if (visited.get(c) == -1) return false; // Do not go back
visited.put(c, -1);
for (char neightbor : map.get(c)) {
if (!dfs(neightbor)) { // False is returned on repeated elements
return false;
}
}
visited.put(c, 1);
sb.insert(0, c); // leaf element, add to buffer
return true;
}
}