0ms C++ solution generating only longest valid strings not using hash map


  • 5
    3

    A counter is use the indicate the difference between the number of ‘(’ and ‘)’. There are several observations to decrease the running time:

    If we remove ‘(’ at index “i”, then we should also remove the following consecutive ‘(’ to avoid duplicate solution.

    The same principle works for ‘)’.

    To get the longest valid string, we should try not delete a certain character first.

    During the DFS, if we observe that the string to be obtained without removing any more characters is shorter than the max length of the solution, we should stop searching.

    We can use ‘)’ only when the counter is larger than 0.

    We can use ‘(’ only when the remaining ‘)’ is more than the counter.

    We can ignore ‘)’ only when the the remaining ‘)’ is not less than the counter.

    class Solution {
    public:
        vector<string> removeInvalidParentheses(string s) {
            maxAnsLen = 0;
            strLen = s.size();
            cnt = 0;
            str = s;
            tmp = "";
            
            numAntiP = new int [strLen + 1];
            jump = new int [strLen + 1];
            numAntiP[strLen] = 0;
            jump[strLen] = strLen;
            str.push_back('@');
            for (int i = strLen - 1; i >= 0; i--) {
                numAntiP[i] = numAntiP[i + 1] + (str[i] == ')');
                if (str[i] == ')')
                    jump[i] = (str[i + 1] == ')') ? jump[i + 1] : (i + 1);
                if (str[i] == '(')
                    jump[i] = (str[i + 1] == '(') ? jump[i + 1] : (i + 1);
            }
    
            dfs(0);
            return ans;
        }
    private:
        int cnt, *numAntiP, *jump, strLen, maxAnsLen;
        vector<string> ans;
        string str, tmp;
        void dfs(int i) {
            if (strLen - i + tmp.size() < maxAnsLen)
                return;
            else if (i == strLen) {
                maxAnsLen = tmp.size();
                ans.push_back(tmp);
            }
            else if (str[i] == ')') {
                if (cnt > 0) {
                    cnt--;
                    tmp.push_back(str[i]);
                    dfs(i + 1);
                    tmp.pop_back();
                    cnt++;
                }
                if (numAntiP[i + 1] >= cnt)
                    dfs(jump[i]); 
            }
            else if (str[i] == '(') {
                if (numAntiP[i + 1] > cnt) {
                    cnt++;
                    tmp.push_back(str[i]);
                    dfs(i + 1);
                    tmp.pop_back();
                    cnt--;
                }
                dfs(jump[i]); 
            }
            else {
                tmp.push_back(str[i]);
                dfs(i + 1);
                tmp.pop_back();
            }
        }
    };

  • 0
    N

    What would be the time and space complexity for this solution ?


Log in to reply
 

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