# 【LeetCode】 678. Valid Parenthesis String

## Description
> 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.

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

> 給予一個字串只包含三種字元：`(`、`)`和`*`，寫一個function去檢查這個字串是否合法。我們根據以下規則去定義字串是否合法：

> 1. 一個左括號`(`必須對應到一個右括號`)`。
> 2. 一個右括號`)`必須對應到一個左括號`(`。
> 3. 左括號`(`必須在對應的右括號`)`之前出現。
> 4. `*`可以當作是一個右括號`)`或是一個左括號`(`或是空的字串。
> 5. 空字串也是合法的。

> 注意：
字串大小在1到100之間。

## Example:

Example 1:
Input: "()"
Output: True

Example 2:
Input: "(*)"
Output: True


Example 3:
Input: "(*))"
Output: True

## Solution

* 在寫這題之前，最好先會一般括號匹配的題目(就是沒有`*`)。
* 我們一樣使用堆疊解法：掃描一次原字串，遇到`(`和`*`的時候放入堆疊，而遇到`)`時去檢查堆疊。
* 檢查的時候根據三個原則：
* 如果堆疊為空，代表出現無法匹配的`)`，不合法。
* 如果有`(`也有`*`在堆疊中，優先拿出`(`。
* 因為是堆疊，記得要從後面放入的開始拿。
* 掃描完之後還沒有結束，我們只檢查了所有`*`當作`(`的部分。接著要檢查堆疊剩下來的東西是否合法。
* 因為`*`在這個階段只會變成`)`或是空字串，那麼我們可以想成所有的`*`都是`)`，但是有剩下來的也無妨。
* 假設原字串是`((***`，改為`(()))`去想，並且多餘的`)`也當作合法就好了！
* 如果是`**(`就會變成`))(`，這樣就不合法。

---

* 下面的範例code中，使用C++的`string`當作堆疊，並且用了`rfind()`和`replace()`等等的炫技。
* 其實也就只是找到最後面的`(`並移除而已，不用太緊張XD
* 後段的檢查也直接用比較偏簡化的方式解，其實就是直接去算`(`和`*`的個數，就沒有再換成`)`之類的了。(上面只是方便理解，實務上那樣做沒有什麼意義而且會變慢)

### Code

class Solution {
public:
    bool checkValidString(string s) {
        string stack;
        for(int i = 0; i < s.length(); i++)
        {
            if(s[i] == ')')
            {
                if(stack.empty())
                    return false;
                auto it = stack.rfind('(');
                if(it != std::string::npos)
                    stack.replace(it, 1, "");
                else
                {
                    it = stack.rfind('*');
                    stack.erase(it);
                }
            }
            else
                stack += s[i];
        }
        int star = 0;
        for(int i = 0; i < stack.length(); i++)
        {
            if(stack[i] == '(') star--;
            else star++;
            star = min(star, 0);
        }
        return star == 0;
    }
};

###### tags: `LeetCode` `C++`