simple C++ O(n) solution,3ms


  • 0
    C

    This question is like the leetcode 20 Valid Parentheses. We can use stack to solve. The different is '* ' in the string. But we can change the question to another question. For example,
    (* )=* +()
    |* (* (* ()))=* * * +((()))
    So, we can move "* " to stack bottom. First, we slove the right, it is easy. Then we solve the right.

    class Solution {
    public:
     void getD(stack<char> *strings)
        {
            stack<char> temp;
            bool flag = false;
            while (!strings->empty() && !flag)
            {
                char current = strings->top();
                strings->pop();
                if (current == '(')
                    flag = true;
                else
                    temp.push(current);
            }
            while (!temp.empty())
            {
                strings->push(temp.top());
                temp.pop();
            }
            if (!flag)
                strings->pop();
        }
        bool checkValidString(string s) {
            stack<char> stringstack;
            for (int i = 0; i < s.length(); i++)
            {
                if (s[i] !=')')
                    stringstack.push(s[i]);
                else 
                {
                    if (!stringstack.empty())
                        getD(&stringstack);
                    else
                        return false;
                }	
            }
            stack<char> stringstack2;
            while (!stringstack.empty()){
                char topchar = stringstack.top();
                stringstack.pop();
                if (topchar == '(')
                {
                    if (stringstack2.empty())
                        return false;
                    else
                        stringstack2.pop();
                }
                else
                    stringstack2.push(topchar);
            }
            return true;		 
        }
    };
    

Log in to reply
 

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