678.有效的括号字符串

题目

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串。

示例 1:

输入: “()”
输出: True

示例 2:

输入: “(*)”
输出: True

示例 3:

输入: “(*))”
输出: True

注意:

1. 字符串大小将在 [1，100] 范围内。

   思路

   主要是(和*的问题。
   总体思路：(和*分别按照相同和相对来看，最后比较记录的(与*相同与不同时的数量即可。
   可以用栈，也可以直接记录，毕竟栈在这里的用途也是记录(和*的数量的。
   lo记录(与*不同时的数量，hi记录(和*相同时的数量。因此当hi<0的时候一定不行（有括号大于做括号和*之和）
   整个遍历结束后，hi肯定是要>=0的，这个时候只需要看lo就可以了，如果lo<=0，那么说明(的数量小鱼等于*的数量，*经过变换可以抵消所有的(。

   代码

   class Solution {
   public:
       bool checkValidString(string s) {
           int lo = 0, hi = 0;
           for(char c:s){
               if(c=='('){
                   lo++;
                   hi++;
               }else if(c==')'){
                   lo = max(0,lo-1);
                   hi--;
                   if(hi<0) return false;
               }else{
                   lo = max(0,lo-1);
                   hi++;
               }
           }
           return lo<=0;
   
       }
   };