678.Valid Parenthesis String

Tags: String Medium

Links: https://leetcode.com/problems/valid-parenthesis-string/

---

Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Example 1:

Input: "()"
Output: True

Example 2:

Input: "(*)"
Output: True

Example 3:

Input: "(*))"
Output: True

Note:

1. The string size will be in the range [1, 100].

---

class Solution {
public:
    bool checkValidString(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        stack<int> parenthesis, star;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            switch(s[i]) {
                case '(' :
                    parenthesis.push(i);
                    break;
                case ')' :
                    if (parenthesis.empty() && star.empty()) return false;
                    if (!parenthesis.empty()) parenthesis.pop();
                    else star.pop();
                    break;
                default: star.push(i);
            }
        }

        while (!parenthesis.empty()) {
            if (star.empty() || parenthesis.top() > star.top()) return false;
            parenthesis.pop(); star.pop();
        }

        return true;
    }
};

用一个栈parenthesis存储左括号的下标，用star存储*所在的下标，当出现一个右括号的时候，能和它匹配的只有左括号和*，那么优先弹出左括号，否则用*匹配。如果无法完成匹配，则返回false。

最好的结果自然是左括号的栈为空，但是不为空的时候，去用*匹配，但是得保证，*的要出现在左括号的右边才能完成匹配。