【数据结构-合法括号字符串】力扣678. 有效的括号字符串

给你一个只包含三种字符的字符串，支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串，如果是 有效 字符串返回 true 。

有效 字符串符合如下规则：

任何左括号 ‘(’ 必须有相应的右括号 ‘)’。
任何右括号 ‘)’ 必须有相应的左括号 ‘(’ 。
左括号 ‘(’ 必须在对应的右括号之前 ‘)’。
‘*’ 可以被视为单个右括号 ‘)’ ，或单个左括号 ‘(’ ，或一个空字符串 “”。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “(*)”
输出：true

示例 3：
输入：s = “(*))”
输出：true

提示：
1 <= s.length <= 100
s[i] 为 ‘(’、‘)’ 或 ‘*’

栈

class Solution {
public:bool checkValidString(string s) {stack<int> st1;stack<int> st2;for(int i = 0; i < s.size(); i++){int c = s[i];if(c == '('){st1.push(i);}else if(c == '*'){st2.push(i);}else if(c == ')'){if(!st1.empty()){st1.pop();}else if(!st2.empty()){st2.pop();}else return false;}}while(!st1.empty() && !st2.empty()){int k1 = st1.top();int k2 = st2.top();st1.pop();st2.pop();if(k1 > k2){return false;}}return st1.empty();}
};

时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串一次，遍历过程中每个字符的操作时间都是 O(1)，遍历结束之后对左括号栈和星号栈弹出元素的操作次数不会超过 n。

空间复杂度：O(n)，其中 n 是字符串 s 的长度。空间复杂度主要取决于左括号栈和星号栈，两个栈的元素总数不会超过 n。

这道题，我们可以定义两个栈，一个栈用来储存未匹配的左括号的索引，一个栈用来储存星号的索引。当我们遍历到左括号或者星号的时候，我们就将他的索引推入栈中，当我们遍历到右括号的时候，我们优先将他与左括号进行匹配，没有左括号我们才用星号去匹配。

遍历完字符串了以后，可能会存在还有未匹配的左括号，我们要做的就是将他与星号进行匹配，那么我们就记录栈顶元素，也就是他们各自的索引，由于星号这时候充当的是变成右括号，那么星号的索引必定要大于左括号才可以，如果st1的栈顶索引大于st2的栈顶索引，那么就会返回false，因为这时候找不到一个星号和这个左括号进行匹配。

最后返回st1.empty()，即当st1中的左括号和星号匹配后，依旧还有剩余，那么就是false，如果st1为空，那么就返回true。

贪心

class Solution {
public:bool checkValidString(string s) {int minCount = 0, maxCount = 0;int n = s.size();for(int i = 0; i < n; i++){char c = s[i];if(c == '('){minCount++;maxCount++;}else if(c == ')'){minCount = max(minCount-1, 0);maxCount--;if(maxCount < 0) return false;}else{maxCount++;minCount = max(minCount-1, 0);}}return minCount == 0;}
};

时间复杂度：O(n)，其中 n 是字符串 s 的长度。需要遍历字符串一次。
空间复杂度：O(1)。

minCount：表示可能的最低括号数。它考虑了 ‘’ 可以为 ‘)’ 的情况，用于平衡括号。
maxCount：表示可能的最高括号数。它考虑了 '’ 可以为 ‘(’ 的情况，用于平衡括号。

任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，说明没有左括号可以和右括号匹配，返回 false。