Alien Dictionary
Alien Dictionary
先说一个自己写这题时犯的错误,就是建 class 的时候没直接建 Node ,而是建了个 Edge,再用 Edge 去建 ArrayList[] 代表 Graph,太麻烦了,只是在故意贴近之前写题的模板而已,因为那几题给的都是 edges.
要自己从头建 Graph ,就应该直接从 Node 写起,记 state, children, indegree 都方便。
题意解析:
- 同一个单词中的字母先后顺序没有任何意义;
- 相邻单词之间,按照 Lexicographical order 排列的意义是,双方字符串中第一个不 match 的字符代表这一条 directed edge,即字符的先后顺序;
- 如果所有字符一致,但是其中一个单词长一些,也无法学习到 edge, 但是多出来的那个字符要记得加入字典 ,暂时作为一个独立 node;
- 如果发现字典 Graph 中有环,返回空字符串;
- 如果字典中只有一个单词,返回此单词的任意顺序皆可;
- 加入新 edge 的时候,记得判重,不要加入重复 child 节点;
BFS解法步骤
- 比较连续的两个字符串, 找到第一个不相同的字符后, 用min len, 建立图. 注意找到字符要break, 不要乱学edge
- 找出degree为0的点加入queue
- BFS开始
public 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;
}
}
DFS解法如出一辙. 只是建立图的时候, BFS是存degree map, DFS是存state map. 因为这题不保证sort map一定存在, 所以dfs的时候要返回boolean来check cycle
犯了一个错误是 建立graph的时候, graph里每一个点都要有对应, map.get(key)对应的neighbor set可以为空. BFS这里不需要. 写法上稍有差异, BFS通过 if map contains判断了
一次AC
public class Solution {
public String alienOrder(String[] words) {
Map<Character, Set<Character>> map=new HashMap<Character, Set<Character>>();
Map<Character, Integer> state=new HashMap<Character, Integer>();
StringBuilder sb = new StringBuilder();
if(words==null || words.length==0) return sb.toString();
for(String s: words){
for(char c: s.toCharArray()){
state.put(c,0);
map.put(c, new HashSet<Character>());
}
}
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);
}
break;
}
}
}
for(Character key : map.keySet()){
if(state.get(key)==0)
if(dfs(key, map, state, sb)) return "";
}
return sb.toString();
}
public boolean dfs(Character key, Map<Character, Set<Character>> map, Map<Character, Integer> state, StringBuilder sb){
boolean cycle = false;
state.put(key, 1);
for(Character neighbor: map.get(key)){
if(state.get(neighbor)==1) return true;
else if(state.get(neighbor)==0)
cycle = cycle||dfs(neighbor, map, state, sb);
}
state.put(key, 2);
sb.insert(0, key);
return cycle;
}
}