Algorithm Notes
  • Introduction
  • Search & Backtracking 搜索与回溯
    • Tree 与 BackTracking 的比较
    • Subsets, Combination 与 Permutation
    • Subsets & Combinations & Combination Sum
    • 枚举法
    • N 皇后 + 矩阵 Index Trick
    • Sudoku 数独 + 矩阵 Index Trick
    • Word Ladder I & II
    • Number of ways 类
    • DFS flood filling
    • Strobogrammatic 数生成
    • String 构造式 DFS + Backtracking
    • Word Pattern I & II
    • (G) Binary Watch
    • (FB) Phone Letter Combination
    • 常见搜索问题的迭代解法
  • String,字符串类
    • 多步翻转法
    • Substring 结构和遍历
    • Palindrome 问题
    • Palindrome Continued
    • String / LinkedList 大数运算
    • 序列化与压缩
    • 5/24 String 杂题
    • Knuth–Morris–Pratt 字符串匹配
    • Lempel–Ziv–Welch 字符串压缩算法
    • (G) Decode String
    • (G) UTF-8 Validation
  • Binary Tree,二叉树
    • 各种 Binary Tree 定义
    • LCA 类问题
    • 三序遍历,vertical order
    • Post order traversal 的应用
    • Min/Max/Balanced Depth
    • BST
    • 子树结构
    • Level Order traversal
    • Morris 遍历
    • 修改结构
    • 创建 / 序列化
    • 子树组合,BST query
    • 路径与路径和
    • NestedInteger 类
    • (FB) 从 Binary Tree Path 看如何递归转迭代
    • (FB) Binary Tree Path 比较路径大小
    • 比较好玩的 Binary Tree 概率题
  • Segment & Fenwick Tree,区间树
    • Segment Tree 基础操作
    • Segment Tree 的应用
    • Fenwick Tree (Binary Indexed Tree)
    • Range Sum Query 2D - Immutable
  • Union-Find,并查集
    • Union-Find,并查集基础
    • Union-Find, 并查集应用
  • Dynamic Programming, 动态规划
    • 6/20, 入门 House Robber
    • 7/12, Paint Fence / House
    • 6/24, 滚动数组
    • 6/24, 记忆化搜索
    • 6/24, 博弈类 DP
    • 博弈类DP, Flip Game
    • 6/25, 区间类DP
    • 6/27, subarray 划分类,股票
    • 7/2, 字符串类
    • Bomb Enemies
    • 8/2,背包问题
    • (G) Max Vacation
    • (11/4新增) AST 子树结构 DP
  • LinkedList,链表
    • 6/9, LinkedList,反转与删除
    • 6/11, LinkedList 杂题
    • (FB) 链表的递归与倒序打印
  • LinkedIn 面经,算法题
    • 6/17, LinkedIn 面经题
    • 6/28, LinkedIn 面经题
    • 7/6, LinkedIn 面经
    • Shortest Word Distance 类
    • DFA Parse Integer
  • Two Pointers,双指针
    • 3 Sum, 3 Sum Closest / Smaller, 4 Sum
    • 对撞型,灌水类
    • 对撞型,partition类
    • Wiggle Sort I & II
    • 双指针,窗口类
    • 双指针,窗口类
    • Heap,排序 matrix 中的 two pointers
  • Bit & Math,位运算与数学
    • Bit Manipulation,对于 '1' 位的操作
    • Math & Bit Manipulation, Power of X
    • 坐标系 & 数值计算类
    • Add Digits
    • 用 int 做字符串 signature
  • Interval 与 扫描线
    • Range Addition & LCS
    • 7/5, Interval 类,扫描线
  • Trie,字典树
    • 6/9, Trie, 字典树
  • 单调栈,LIS
    • 4/13 LIS
    • 栈, 单调栈
    • Largest Divisible Subset
  • Binary Search 类
    • Matrix Binary Search
    • Array Binary Search
    • Find Peak Element I & II
    • **Median of Two Sorted Arrays
  • Graph & Topological Sort,图 & 拓扑排序
    • 有向 / 无向 图的基本性质和操作
    • 拓扑排序, DFS 做法
    • 拓扑排序, BFS 做法
    • Course Schedule I & II
    • Alien Dictionary
    • Undirected Graph, BFS
    • Undirected Graph, DFS
    • 矩阵,BFS 最短距离探索
    • 欧拉回路,Hierholzer算法
    • AI, 迷宫生成
    • AI, 迷宫寻路算法
    • (G) Deep Copy 无向图成有向图
  • 括号与数学表达式的计算
  • Iterator 类
  • Majority Element,Moore's Voting
  • Matrix Inplace Operations
  • 常见数据结构设计
  • (G) Design / OOD 类算法题
  • 随机算法 & 数据结构
  • (FB) I/O Buffer
  • (FB) Simplify Path, H-Index I & II
  • (FB) Excel Sheet, Remove Duplicates
  • Integer 的构造,操作,序列化
  • Frequency 类问题
  • Missing Number 类,元素交换,数组环形跳转
  • 8/10, Google Tag
  • (FB) Rearrange String k Distance Apart
  • Abstract Algebra
    • Chap1 -- Why Abstract Algebra ?
    • Chap2 -- Operations
    • Chap3 -- The Definition of Groups
Powered by GitBook
On this page
  • Alien Dictionary
  • 要自己从头建 Graph ,就应该直接从 Node 写起,记 state, children, indegree 都方便。
  • 题意解析:
  • 同样的结构, BFS 写法:
  • 不建 Node class 而用 HashMap 的做法如下:
  • 自己在写这题白板的时候犯了一个小错误,就是一旦发现了 char1 != char2 ,处理完了要记得 break,不要乱学新的 edge 出来。

Was this helpful?

  1. Graph & Topological Sort,图 & 拓扑排序

Alien Dictionary

PreviousCourse Schedule I & IINextUndirected Graph, BFS

Last updated 4 years ago

Was this helpful?

先说一个自己写这题时犯的错误,就是建 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(): "";
    }
Alien Dictionary