題目： LeetCode - 678. Valid Parenthesis String

題目說明

給一個字串，裡面只會有三種字元，(、)、*，要求檢驗字串是否有效。字串有效須滿足以下條件：

  • 任何的左括弧必須要有對應的右括弧
  • 任何的右括弧必須要有對應的右括弧
  • 左括弧必須在對應的右括弧前面

※ * 號可代表左括弧、右括弧或空字元。

解題思路

可想像成左括弧會與最近的右括弧相消，所以使用一個 count 來記數，碰到左括弧就 + 1，碰到右括弧就 - 1。但是由於還有一個 * 號，而 * 可以是左括弧、右括弧或空字元，所以它可能會 + 1、- 1、或不變，以至於我們的 count 會是一個範圍，所以使用 max、 min 來做記數。在碰到括弧時一樣正常的 + 1、- 1，但碰到 * 號的話，max + 1、min - 1，而在做的期間 max 不可小於 0，因為 max 小於 0 的話代表會有右括弧前面沒有對應的左括弧，那這個字串就一定不是有效的，所以就直接回傳 False，而 min 也不能小於 0，因為 min 若是 0 的話代表 * 號只能當作左括弧或空字元，不能是右括弧。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool checkValidString(string s) {
        int max = 0, min = 0;
        for(auto& i : s)
        {
            if(i == '(')
                ++min, ++max;
            else if(i == ')')
                --min, --max;
            else if(i == '*')
                --min, ++max;
            if(max < 0)
                return false;
            if(min < 0)
                min = 0;
        }
        return min == 0;
    }
};