Day 106, ##， Course Schedule, Implement Trie (Prefix Tree)

Course Schedule

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?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:

1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

-------------------------------------------------------------
重点：缺乏知识点，topological ordering的BFS做法https://en.wikipedia.org/wiki/Topological_sorting#Algorithms
Detect if there is a cycle in directed graph,
BFS

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int> > edges(numCourses);
        vector<int> inDegree(numCourses,0);
        queue<int> que;
         
        for (int i = 0; i < prerequisites.size(); i++) {
            edges[prerequisites[i].second].push_back(prerequisites[i].first);
            inDegree[prerequisites[i].first]++;
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                que.push(i);
            }
        }
        
        while (!que.empty()) {
            int current = que.front();
            que.pop();
            for (int i = 0; i < edges[current].size(); i++) {
                inDegree[edges[current][i]]--;
                if (inDegree[edges[current][i]] == 0) {
                    que.push(edges[current][i]);
                }
            }
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] != 0) {
                return false;
            }
        }
        
        return true;
    }
};

DFS

class Solution {
public:
    bool dfs(vector<vector<int> > &edges, vector<int> &visit, int point) {
        if (visit[point] == -1) return false;
        if (visit[point] == 1) return true;
        
        visit[point] = -1;
        for (int i = 0; i < edges[point].size(); i++) {
            if (!dfs(edges,visit,edges[point][i])) {
                return false;
            }
        }
        visit[point] = 1;
        return true;
    }

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> visit(numCourses,0);
        vector<vector<int> > edges(numCourses);
        
        for (int i = 0; i < prerequisites.size(); i++) {
            edges[prerequisites[i].second].push_back(prerequisites[i].first);
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(edges,visit,i)) return false;
        }
        
        return true;
    }
};

Java, updated on Sep-29th-2018

class Solution {
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = builtGraph(numCourses, prerequisites);
        int[] visited = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, i, visited)) return false;
        }
        
        return true;
    }
    
    private boolean dfs(List<List<Integer>> graph, int num, int[] visited) {
        if (visited[num] == 1) return true;
        if (visited[num] == -1) return false;
        
        visited[num] = -1;
        for (int nei : graph.get(num)) {
            if (!dfs(graph, nei, visited)) return false;
        }
        
        visited[num] = 1;
        return true;
    }
    
    private List<List<Integer>> builtGraph(int numCourses, int[][] prerequisites) {
        List<List<Integer>> rt = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            rt.add(new ArrayList<>());
        }
        
        for (int[] edge : prerequisites) {
            rt.get(edge[1]).add(edge[0]);
        }
        
        return rt;
    }

}

BFS, Java
O(n), n是edge的数量，复杂度跟DFS一样

class Solution {
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> rt = new ArrayList<>();
        int[] inEdges = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            rt.add(new ArrayList<>());
        }
        
        for (int[] edge : prerequisites) {
            rt.get(edge[1]).add(edge[0]);
            inEdges[edge[0]]++;
        }
        
        Queue<Integer> que = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < numCourses; i++) {
            if (inEdges[i] == 0) {
                que.add(i);
            }
        }
        
        while (!que.isEmpty()) {
            int top = que.poll();
            for (int i : rt.get(top)) {
                inEdges[i]--;
                count++;
                if (inEdges[i] == 0) {
                    que.add(i);
                }
            }
        }
        
        return count == prerequisites.length;
    }
}

Implement Trie (Prefix Tree)

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

Note:
You may assume that all inputs are consist of lowercase letters a-z.

---------------------------------------------
在判断terminal上代码可以更简化

class TrieNode {
public:
    
    // Initialize your data structure here.
    TrieNode() {
        next = vector<TrieNode*>(26,NULL);
        terminal = false;
    }

    char value;
    vector<TrieNode*> next;
    bool terminal;
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode *cur = root;
        for (int i = 0; i < s.length(); i++) {
            char c = s[i] - 'a';
            if (cur->next[c] == NULL) {
                TrieNode *trie = new TrieNode();
                trie->value = c;
                cur->next[c] = trie;
            }
            if (i == s.length() - 1) {
             cur->next[c]->terminal = true;
            }
            cur = cur->next[c];
        }
    }

    // Returns if the word is in the trie.
    bool search(string key) {
        TrieNode *cur = root;
        for (int i = 0; i < key.length(); i++) {
            char c = key[i] - 'a';
            if (cur->next[c] == NULL) {
                return false;
            }
            if (i == key.length() - 1 && cur->next[c]->terminal) {
                return true;
            } 
            
            cur = cur->next[c];
        }
        
        return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix[i] - 'a';
            if (cur->next[c] == NULL) {
                return false;
            }
            
            cur = cur->next[c];
        }
        
        return true;
    }

private:
    TrieNode* root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

Java, updated on July-8th-2018

class Trie {
    class Node{
        public Map<Character, Node> next;
        public boolean isWord;
        public Node() {
            next = new HashMap<>();    
        }
    }
    
    private Node root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new Node();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.next.containsKey(c)) {
                node.next.put(c, new Node());
            }
            node = node.next.get(c);
        }
        node.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Node node = getThatNode(word);
        return node != null && node.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return getThatNode(prefix) != null;
    }
    
    private Node getThatNode(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!node.next.containsKey(c)) return null;
            node = node.next.get(c);
        }
        
        return node;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */