Alien Dictionary
先说一个自己写这题时犯的错误，就是建 class 的时候没直接建 Node ，而是建了个 Edge，再用 Edge 去建 ArrayList[] 代表 Graph，太麻烦了，只是在故意贴近之前写题的模板而已，因为那几题给的都是 edges.
要自己从头建 Graph ，就应该直接从 Node 写起，记 state, children, indegree 都方便。
题意解析：
同一个单词中的字母先后顺序没有任何意义；
相邻单词之间，按照 Lexicographical order 排列的意义是，双方字符串中第一个不 match 的字符代表这一条 directed edge，即字符的先后顺序；
如果所有字符一致，但是其中一个单词长一些，也无法学习到 edge，但是多出来的那个字符要记得加入字典，暂时作为一个独立 node;
如果发现字典 Graph 中有环，返回空字符串；
如果字典中只有一个单词，返回此单词的任意顺序皆可；
加入新 edge 的时候，记得判重，不要加入重复 child 节点；
超过 69% 的 DFS 写法：
public class Solution {
private class Node{
int chrInt;
int state;
int indegree;
ArrayList<Integer> children;
public Node(int chrInt){
this.chrInt = chrInt;
state = 0;
indegree = 0;
children = new ArrayList<Integer>();
}
public char getChar(){
return (char) (this.chrInt + 'a');
}
}
public String alienOrder(String[] words) {
HashMap<Integer, Node> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
if(words.length == 1) return words[0];
for(int i = 0; i < words.length - 1; i++){
learn(words[i], words[i + 1], map);
}
for(int i : map.keySet()){
if(map.get(i).state == 0 && dfs(i, sb, map)) return "";
}
return sb.reverse().toString();
}
private boolean dfs(int cur, StringBuilder sb, HashMap<Integer, Node> map) {
Node node = map.get(cur);
node.state = 1;
boolean hasCycle = false;
for(int i = 0; i < node.children.size(); i++){
int next = node.children.get(i);
if(map.get(next).state == 1) hasCycle = true;
else if (map.get(next).state == 0) {
hasCycle = hasCycle || dfs(next, sb, map);
}
}
node.state = 2;
sb.append(node.getChar());
return hasCycle;
}
private void learn(String word1, String word2, HashMap<Integer, Node> map){
int ptr1 = 0;
int ptr2 = 0;
while(ptr1 < word1.length() && ptr2 < word2.length()){
int parent = word1.charAt(ptr1++) - 'a';
int child = word2.charAt(ptr2++) - 'a';
if(!map.containsKey(parent)) map.put(parent, new Node(parent));
if(!map.containsKey(child)) map.put(child, new Node(child));
if(parent != child){
Node p = map.get(parent);
Node c = map.get(child);
if(!p.children.contains(child)){
p.children.add(child);
c.indegree ++;
}
break;
}
}
while(ptr1 < word1.length()){
int node = word1.charAt(ptr1++) - 'a';
if(!map.containsKey(node)) map.put(node, new Node(node));
}
while(ptr2 < word2.length()){
int node = word2.charAt(ptr2++) - 'a';
if(!map.containsKey(node)) map.put(node, new Node(node));
}
}
}同样的结构， BFS 写法：
public class Solution {
private class Node{
int chrInt;
int state;
int indegree;
ArrayList<Integer> children;
public Node(int chrInt){
this.chrInt = chrInt;
state = 0;
indegree = 0;
children = new ArrayList<Integer>();
}
public char getChar(){
return (char) (this.chrInt + 'a');
}
}
public String alienOrder(String[] words) {
HashMap<Integer, Node> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
if(words.length == 1) return words[0];
for(int i = 0; i < words.length - 1; i++){
learn(words[i], words[i + 1], map);
}
Queue<Node> queue = new LinkedList<>();
int total = 0;
for(int i : map.keySet()){
total++;
if(map.get(i).indegree == 0) queue.offer(map.get(i));
}
int count = 0;
while(!queue.isEmpty()){
Node cur = queue.poll();
sb.append(cur.getChar());
count ++;
for(int next : cur.children){
Node child = map.get(next);
child.indegree--;
if(child.indegree == 0) queue.offer(child);
}
}
return (count == total) ? sb.toString() : "" ;
}
private void learn(String word1, String word2, HashMap<Integer, Node> map){
int ptr1 = 0;
int ptr2 = 0;
while(ptr1 < word1.length() && ptr2 < word2.length()){
int parent = word1.charAt(ptr1++) - 'a';
int child = word2.charAt(ptr2++) - 'a';
if(!map.containsKey(parent)) map.put(parent, new Node(parent));
if(!map.containsKey(child)) map.put(child, new Node(child));
if(parent != child){
Node p = map.get(parent);
Node c = map.get(child);
if(!p.children.contains(child)){
p.children.add(child);
c.indegree ++;
}
break;
}
}
while(ptr1 < word1.length()){
int node = word1.charAt(ptr1++) - 'a';
if(!map.containsKey(node)) map.put(node, new Node(node));
}
while(ptr2 < word2.length()){
int node = word2.charAt(ptr2++) - 'a';
if(!map.containsKey(node)) map.put(node, new Node(node));
}
}
}不建 Node class 而用 HashMap 的做法如下：
自己在写这题白板的时候犯了一个小错误，就是一旦发现了 char1 != char2 ，处理完了要记得 break，不要乱学新的 edge 出来。
public String alienOrder(String[] words) {
HashMap<Character, Set<Character>> graphMap = new HashMap<>();
HashMap<Character, Integer> indegreeMap = new HashMap<>();
for(String str : words){
for(int i = 0; i < str.length(); i++){
indegreeMap.put(str.charAt(i), 0);
graphMap.put(str.charAt(i), new HashSet<>());
}
}
for(int i = 0; i < words.length - 1; i++){
String word1 = words[i];
String word2 = words[i + 1];
for(int index = 0; index < Math.min(word1.length(),
word2.length()); index++){
char char1 = word1.charAt(index);
char char2 = word2.charAt(index);
if(char1 != char2){
Set<Character> neighbours = graphMap.get(char1);
if(!neighbours.contains(char2)){
int indegree = indegreeMap.get(char2);
indegreeMap.put(char2, indegree + 1);
}
graphMap.get(char1).add(char2);
break;
}
}
}
StringBuilder sb = new StringBuilder();
Queue<Character> queue = new LinkedList<>();
for(Character chr : indegreeMap.keySet()){
if(indegreeMap.get(chr) == 0) queue.offer(chr);
}
int count = 0;
while(!queue.isEmpty()){
char curChar = queue.poll();
count ++;
sb.append(curChar);
for(Character child : graphMap.get(curChar)){
int degree = indegreeMap.get(child);
degree --;
indegreeMap.put(child, degree);
if(degree == 0) queue.offer(child);
}
}
return (count == graphMap.keySet().size()) ? sb.toString(): "";
}Last updated