【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++