simple C++ O(n) solution, greedy


  • 1
    class Solution {
    public:
        bool checkValidString(string s) {
            // greedy
            // number of '*' appear between each '('
            int star = 0; 
            stack<int> left;
            for (int i = 0; i < s.size(); ++i) {
                if (s[i] == '*') {
                    ++star;
                } else if (s[i] == '(') {
                    left.push(star);
                    star = 0;
                } else if (s[i] == ')') {
                    if (!left.empty()) {
                        star += left.top();
                        left.pop();
                    } else if (star > 0) {
                        --star;
                    } else {
                        return false;
                    }
                }
            }
            // check if still '(' left
            while (!left.empty() && star > 0) {
                star += left.top() - 1;
                left.pop();            
            }
            return left.empty() && star >= 0;
        }
    };
    

Log in to reply
 

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