exact the same algorithm, accepted in C++ but TLE in Python?


  • 0
    X

    C++:

    
    #include <unordered_map>
    #include <vector>
    #include <list>
    #include <algorithm>
    #include <numeric>
    using namespace std;
    
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int> >& prerequisites) {
            auto board = new bool[numCourses];
            for (int i = 0; i != numCourses; ++i) {
                board[i] = true;
            }
            unordered_map<int, list<int> > predict;
            for (auto& pair : prerequisites) {
                board[pair.second] = false;
                predict[pair.second].push_back(pair.first);
            }
    
            bool updated;
            do {
                updated = false;
                for (int i = 0; i != numCourses; ++i) {
                    if (!board[i]) {
                        predict[i].remove_if([&](int j){return board[j];});
                        if (predict[i].empty()) {
                            board[i] = true;
                            updated = true;
                        }
                    }
                }
            } while (updated);
            
            for (int i = 0; i < numCourses; ++i) {
                if (!board[i]) return false;
            }
            return true;
        }
        
    };
    
    

    Python:

    
    from collections import defaultdict
    import array
    import operator
    
    class Solution(object):
        def canFinish(self, numCourses, prerequisites):
            board = [True for _ in range(numCourses)] #True for ok to take, False for not ok: need prerequisites
            predict = defaultdict(list)#dict: {int : [int]}
            for prerequisite in prerequisites:
                board[prerequisite[1]] = False # prerequisite[1] need prerequisites
                predict[prerequisite[1]].append(prerequisite[0]) #assume no duplicate edges in input
            
            updated = True
            while (updated):
                updated = False
                for i, val in enumerate(board):
                    if not val: #course i is not ok
                        pres = predict[i] #[int]
                        predict[i] = filter(lambda j: not board[j], pres)
                        if not predict[i]:
                            board[i] = True
                            updated = True
            return reduce(operator.and_, board)
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.