LeetCode(106) -- 207, 208

P207. Course Schedule (Medium)

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

The Best Solution

上次做的时候我认为：“这道题本质上就是问一个有向图中，有没有环的问题。”

其实现在来看，需要加一个重要的条件，就是“这个图不一定是连通的”。一般的DFS或者BFS，都是保证整个图是连通的，那遍历起来其实非常简单。但这个题之所以比较难，就是因为这个图有可能不是连通的。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0) {
            return true;
        }
        
        int[] in = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            in[prerequisites[i][1]]++;
        }
        boolean[] visited = new boolean[prerequisites.length];
        boolean change = true;
        while (change) {
            change = false;
            for (int i = 0; i < prerequisites.length; i++) {
                if (!visited[i]) {
                    if (in[prerequisites[i][0]] == 0 && in[prerequisites[i][1]] != 0) {
                        visited[i] = true;
                        in[prerequisites[i][1]]--;
                        change = true;
                    }
                }
            }
        }
        for (int i = 0; i < numCourses; i++) {
            if (in[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

最优解的算法为以下几步：

1. 创建一个与节点数一样长度的int数组，统计每个节点有多少个子节点。
2. 创建一个与给出的边的数量一样长度的boolean数组，为了记录哪些边被访问/删除过了。
3. 反复地循环/清洗所有的边，只有某一条边没有被访问过，并且这条边的子节点没有子节点了（叶节点），并且这条边的父节点还有子节点（这个节点不是孤立的），那么就把这条边“删除”，访问过，并且父节点的子节点数量减一，并且记录一下这一轮有所改变，下次还要继续循环。这相当于从一棵树的底部不断地向上砍，直到砍成孤立的一个节点或者因为有环没办法再砍为止。
4. 重新检查一遍所有节点的子节点数目，如果有大于0的，说明有环。

当然这道题完全也可以用DFS做，每个节点都遍历一次，如果发现有环，就返回false.

P208. Implement Trie (Prefix Tree) (Medium)

Implement a trie with insert, search, and startsWith methods.

Solution

Trie这个数据结构的用途：

1. google的自动完成
2. 拼写检查
3. IP路由前缀检查
4. T9文本预测
5. 单词游戏

为什么用Trie而不用HashSet呢？

1. 有时候，我们有一个前缀，我们想找到所有这个前缀的单词，用hashset就不好使。
2. 按字母表顺序遍历所有单词，那hashset也不好用。
3. 当单词越来越多时，hashset的时间复杂度可能从O(1)变成O(n)。

用Trie的时间复杂度只有O(m), m是单词的长度。

My Modified Solution

class Trie {

    static class TrieNode {
        private TrieNode[] children = new TrieNode[26];
        private boolean isEnd;
    }

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (curr.children[c - 'a'] == null) {
                curr.children[c - 'a'] = new TrieNode();
            }
            curr = curr.children[c - 'a'];
        }
        curr.isEnd = true;
    }

    private TrieNode searchPrefix(String word) {
        TrieNode curr = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (curr.children[c - 'a'] == null) {
                return null;
            }
            curr = curr.children[c - 'a'];
        }
        return curr;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
}

肯定需要写一个node作为内部类。包括26个children和一个boolean来标记这是不是一个单词。