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;
}

}