Why this code is still very slow? thanks


  • 0
    X
    struct QueueNode {
        string str;
        int level;
        QueueNode(string _str, int _level) : str(_str), level(_level) {}
    };
    
    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            if (s.length() == 0)  {
                return vector<string>(1, "");
            }
            
            vector<string> res;
            set<string> visited;
            queue<QueueNode> q;
            int curLevel = 0;
            int validLevel = -1;
            q.push(QueueNode(s, curLevel));
            bool foundValidOnCurLevel = false;
            
            while (!q.empty()) {
                string curStr = q.front().str; 
                curLevel = q.front().level;
                q.pop();
                
                if(foundValidOnCurLevel && curLevel > validLevel) break;
                
                if (isValid(curStr)) {
                    res.push_back(curStr);
                    foundValidOnCurLevel = true;
                    validLevel = curLevel;
                } else {
                     //push all the strings in current level, by deleting only one '(' or ')'
                    for (int i = 0; i < curStr.length(); i++) {
                        if(curStr[i] == '(' || curStr[i] == ')') {
                            string tmp = curStr.substr(0, i) + curStr.substr(i+1, curStr.length());
                            if (visited.find(tmp) == visited.end()) {
                                q.push(QueueNode(tmp, curLevel + 1));
                                visited.insert(tmp);
                            }
                        }
                    }
                }
            }
            
            return res;
        }
        
        bool isValid(string s) {
            int count = 0;
            for (auto c : s) {
                if (c == '(') {
                    count++;
                } else if(c == ')') {
                    if (count-- == 0) return false;
                }
            }
            return count == 0;
        }
    };
    

    484ms, but I cannot optimize it any more.

    BFS is much slower than DFS?


Log in to reply
 

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