LeetCode678. Valid Parenthesis String(Medium)#Stack

 給定一含括弧字串,內另含*符號,可替代為  (  or  ) or 空字元

字串有效須滿足以下條件：

任何的左括弧必須要有對應的右括弧

任何的右括弧必須要有對應的右括弧

左括弧必須在對應的右括弧前面

可想像成左括弧會與最近的右括弧相消，使用一個 count 來記數，碰到左括弧就 + 1，碰到右括弧就 - 1。但由於還有一個 * 號，而 * 可以是左括弧、右括弧或空字元，所以它可能會 + 1、- 1、或不變，以至於我們的 count 會是一個範圍，所以使用 max、 min 來做記數。

在碰到括弧時一樣正常的 + 1、- 1，但碰到 * 號的話，max + 1、min - 1，而在做的期間 max 不可小於 0，因為 max 小於 0 的話代表會有右括弧前面沒有對應的左括弧，那這個字串就一定不是有效的，所以就直接返回 False，而 min 也不能小於 0，因為 min 若是 0 的話代表 * 號只能當作左括弧或空字元，不能是右括弧。

ans1.

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; } };

Ref:

https://www.cnblogs.com/silentteller/p/12348010.html

https://blog.csdn.net/qq_27060423/article/details/83959401

http://codecrazer.blogspot.com/2017/09/leetcode-678-valid-parenthesis-string.html

https://www.larrysprognotes.com/LeetCode-678/