Alien Dictionary

这道题和Course Schedule的区别：Course Schedule的input是prerequisite[][] 数组，也就是直接给了你edge的关系，所以我们用ArrayList[] 去构造图，ArrayList[i]是图上的每一个点，ArrayList[i]里的所有的点，表示了这些点与i之间是相连的，并且由i指向那些点。因为我们知道ArrayList[]这个array的length是numCourse，所以我们这样子做很方便。如果做DFS，我们就维护一个visited数组，去判断是否有cycle；如果做BFS，就维护一个indree数组，去check每一门课当前的indegree有没有达到0。这些数组的构建的前提都是建立在我们知道numCourses的基础上的。

而在Alien Dictionary里，我们并不知道有多少个distinct character，而且我们也同时需要记录status/indegree的状态，所以我们索性就用OOD的思想去建一个node类（相当于one vertex），把需要的fields都记录在类里。然后当我们每次碰到一个新的character的时候，我们就把一个node的instance给创建出来。并且存在hashmap里，方便后面调用。key就用character做key。

Sample Class Node:

class Node {
  char c;
  int status; // being used when dfs
  int indegree; // being used when bfs
  ArrayList<Character> neighbours;

  public Node(char c) {
    this.c = c;
    status = 0;
    indegree = 0;
    neighbours = new ArrayList<Character>();
  }
}

Alien Dictionary， DFS

public class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Node> map = new HashMap<Character, Node>();

        for (String word: words) {
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!map.containsKey(c)) {
                    map.put(c, new Node(c));
                }
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            int min = Math.min(word1.length(), word2.length());
            boolean foundOrder = false;

            for (int j = 0; j < min; j++) {
                char c1 = word1.charAt(j);
                char c2 = word2.charAt(j);
                if (c1 != c2) {
                    map.get(c1).neighbours.add(c2);
                    foundOrder = true;
                    break;
                }
            }

            if (!foundOrder && word1.length() > word2.length()) {
                return "";
            }
        }

        StringBuffer sb = new StringBuffer();
        for (char c: map.keySet()) {
            Node node = map.get(c);
            if (node.status == 0 && dfs(map, c, sb)) {
                return "";
            }
        }

        return sb.toString();
    }

    private boolean dfs(Map<Character, Node> map, char current, StringBuffer sb) {
        Node node = map.get(current);
        node.status = 1;
        boolean hasCycle = false;

        for (char next: node.neighbours) {
            Node nextNode = map.get(next);
            if (nextNode.status == 1) {
                return true;
            } else if (nextNode.status == 0) {
                hasCycle = hasCycle || dfs(map, next, sb);
            }
        }

        sb.insert(0, current);
        node.status = 2;
        return hasCycle;
    }
}

class Node {
    char c;
    int status;
    int indegree;
    ArrayList<Character> neighbours;

    public Node(char c) {
        this.c = c;
        status = 0;
        indegree = 0;
        neighbours = new ArrayList<Character>();
    }
}

Alien Dictionary, BFS

public class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Node> map = new HashMap<Character, Node>();

        for (String word: words) {
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!map.containsKey(c)) {
                    map.put(c, new Node(c));
                }
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String word1 = words[i];
            String word2 = words[i + 1];
            int min = Math.min(word1.length(), word2.length());
            boolean foundOrder = false;

            for (int j = 0; j < min; j++) {
                char c1 = word1.charAt(j);
                char c2 = word2.charAt(j);
                if (c1 != c2) {
                    map.get(c1).neighbours.add(c2);
                    map.get(c2).indegree++;
                    foundOrder = true;
                    break;
                }
            }

            if (!foundOrder && word1.length() > word2.length()) {
                return "";
            }
        }

        Queue<Character> queue = new LinkedList<Character>();
        for (char c: map.keySet()) {
            if (map.get(c).indegree == 0) {
                queue.offer(c);
            }
        }

        StringBuffer sb = new StringBuffer();
        while (!queue.isEmpty()) {
            char c = queue.poll();
            sb.append(c);

            for (char next: map.get(c).neighbours) {
                map.get(next).indegree--;
                if (map.get(next).indegree == 0) {
                    queue.offer(next);
                }
            }
        }

        return sb.length() == map.size() ? sb.toString() : "";
    }
}

class Node {
    char c;
    int indegree;
    ArrayList<Character> neighbours;

    public Node(char c) {
        this.c = c;
        indegree = 0;
        neighbours = new ArrayList<Character>();
    }
}

还有两种HashMap的DFS/BFS的写法，并且不建这个node类。 如果是DFS，那就维护一个Map>> egdes的关系，同时维护一个Map status的关系，来check是否有cycle。 如果是DFS，同样的需要一个表示edges的map，同时维护一个Map indegree的关系，每次把indegree等于0的character放进queue中去。