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 节点；

超过 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 写法：

不建 Node class 而用 HashMap 的做法如下：

自己在写这题白板的时候犯了一个小错误，就是一旦发现了 char1 != char2 ，处理完了要记得 break，不要乱学新的 edge 出来。

PreviousCourse Schedule I & IINextUndirected Graph, BFS

Last updated

Was this helpful?