05 August 2008
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:
1
2
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Example 2:
1
2
Input: words = ["z","x"]
Output: "zx"
Example 3:
1
2
3
Input: words = ["z","x","z"]
Output: ""
Explanation: The order is invalid, so return "".
Constraints:
这道题让给了我们一些按“字母顺序”排列的单词，但是这个字母顺序不是我们熟知的顺序，而是另类的顺序，让我们根据这些“有序”的单词来找出新的字母顺序，这实际上是一道有向图的问题。跟207 Course Schedule，210 Course Schedule II和630 Course Schedule III类似。理解题目：
1)DFS，建立一个二维的boolean数组g，然后把出现过的字母的对应的位置都赋为true，然后我们把可以推出的顺序的对应位置也赋为true，然后我们就开始递归调用，如果递归函数有返回false的，说明有冲突，则返回false，递归调用结束后结果res中存了入度不为0的字母，最后把入度为0的字母加到最后面，最后把结果result翻转一下即可；
2) BFS
3) Topological Sorting，将词典中字符串的字符两两对比，只有第一个不同的字符才是正确的排序，如ert和wrf，只能推断出e的优先级高于w，剩余字符的优先级不能推断。将字符串的优先级构建为图，然后进行拓扑排序。如果图中无环，则将拓扑排序输出，否则顺序是非法的。
注意对于输入”za”,”zb”,”ca”,”cb”，字符关系为a->b、z->c，输出可以为azbc、zacb，只要输出一种即可。
DFS，参考这里
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
private final int N = 26;
public String alienOrder(String[] words) {
boolean[][] adj = new boolean[N][N];
int[] visited = new int[N];
buildGraph(words, adj, visited);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < N; i++) {
if(visited[i] == 0) { // unvisited
if(!dfs(adj, visited, sb, i)) return "";
}
}
return sb.reverse().toString();
}
public boolean dfs(boolean[][] adj, int[] visited, StringBuilder sb, int i) {
visited[i] = 1; // 1 = visiting
for(int j = 0; j < N; j++) {
if(adj[i][j]) { // connected
if(visited[j] == 1) return false; // 1 => 1, cycle
if(visited[j] == 0) { // 0 = unvisited
if(!dfs(adj, visited, sb, j)) return false;
}
}
}
visited[i] = 2; // 2 = visited
sb.append((char) (i + 'a'));
return true;
}
public void buildGraph(String[] words, boolean[][] adj, int[] visited) {
Arrays.fill(visited, -1); // -1 = not even existed
for(int i = 0; i < words.length; i++) {
for(char c : words[i].toCharArray()) visited[c - 'a'] = 0;
if(i > 0) {
String w1 = words[i - 1], w2 = words[i];
int len = Math.min(w1.length(), w2.length());
for(int j = 0; j < len; j++) {
char c1 = w1.charAt(j), c2 = w2.charAt(j);
if(c1 != c2) {
adj[c1 - 'a'][c2 - 'a'] = true;
break;
}
}
}
}
}
}
BFS，参考这里
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> map=new HashMap<Character, Set<Character>>();
Map<Character, Integer> degree=new HashMap<Character, Integer>();
String result="";
if(words==null || words.length==0) return result;
for(String s: words){
for(char c: s.toCharArray()){
degree.put(c,0);
}
}
for(int i=0; i<words.length-1; i++){
String cur=words[i];
String next=words[i+1];
int length=Math.min(cur.length(), next.length());
for(int j=0; j<length; j++){
char c1=cur.charAt(j);
char c2=next.charAt(j);
if(c1!=c2){
Set<Character> set=new HashSet<Character>();
if(map.containsKey(c1)) set=map.get(c1);
if(!set.contains(c2)){
set.add(c2);
map.put(c1, set);
degree.put(c2, degree.get(c2)+1);
}
break;
}
}
}
Queue<Character> q=new LinkedList<Character>();
for(char c: degree.keySet()){
if(degree.get(c)==0) q.add(c);
}
while(!q.isEmpty()){
char c=q.remove();
result+=c;
if(map.containsKey(c)){
for(char c2: map.get(c)){
degree.put(c2,degree.get(c2)-1);
if(degree.get(c2)==0) q.add(c2);
}
}
}
if(result.length()!=degree.size()) return "";
return result;
}
}
Topological Sorting
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public String alienOrder(String[] words) {
//1.构建图
Map<Character, Set<Character>> map = new HashMap<>();
for (int i = 0; i < words.length - 1; i++) {
for (int j = 0; j < words[i].length() && j < words[i + 1].length(); j++) {
//如果字符相同，比较下一个
if (words[i].charAt(j) == words[i + 1].charAt(j)) continue;
//保存第一个不同的字符顺序
Set<Character> set = map.getOrDefault(words[i].charAt(j), new HashSet<>());
set.add(words[i + 1].charAt(j));
map.put(words[i].charAt(j), set);
break;
}
}
//2.拓扑排序
//创建保存入度的数组
int[] degrees = new int[26];
Arrays.fill(degrees, -1);
//注意，不是26字母都在words中出现，所以出度分为两种情况：没有出现的字母出度为-1，出现了的字母的出度为非负数
for (String str : words) {
//将出现过的字符的出度设定为0
for (char c : str.toCharArray())
degrees[c - 'a'] = 0;
}
for (char key : map.keySet()) {
for (char val : map.get(key)) {
degrees[val - 'a']++;
}
}
//创建StringBuilder保存拓扑排序
StringBuilder sb = new StringBuilder();
//创建一个Queue保存入度为0的节点
Queue<Character> list = new LinkedList<>();
int count = 0;//计算图中节点数
for (int i = 0; i < 26; i++) {
if (degrees[i] != -1) count++;
if (degrees[i] == 0) {
list.add((char) ('a' + i));
}
}
while (!list.isEmpty()) {
Character cur = list.poll();
sb.append(cur);
//将邻接点出度-1
if (map.containsKey(cur)) {
Set<Character> set = map.get(cur);
for (Character c : set) {
degrees[c - 'a']--;
if (degrees[c - 'a'] == 0) list.add(c);
}
}
}
//判断是否有环
if (sb.length() != count) return "";
else return sb.toString();
}
}