题目描述

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

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

输入: "()"
输出: True

错误尝试

计算三者数量，单纯通过数量比较仅能通过部分，左括号必须在右括号前较难实现

class Solution {
    public boolean checkValidString(String s) {
       int count1=countChar('(',s);
       int count2=countChar(')',s);
       int count3=countChar('*',s);
       if(count1==count2){
            return true;
       }else if(Math.abs(count1-count2)<=count3){
            return true;
       }else{
           return false;
       }
    }
    public static int countChar(char searchChar,String s){
        char[] array=s.toCharArray();
        int count=0;
        for(char item:array){
            if(item==searchChar){
                count++;
            }
        }
        return count;
    }
    
}

题解

我们在遍历字符串过程中，设定两个变量lo和hi，分别代表左括号比右括号多的最少个数，和最大个数，那么就有以下结论：

1. 当当前字符为左括号（，那么lo和hi都加1；
2. 当当前字符为∗，那么 2.1. 当lo>0，也就是左括号数量肯定比右括号多了，该∗号通过替换为右括号，显然左括号比右括号多的最少个数需要减1，同时，最大个数加1； 2.2. 否则，最大个数加1即可。
3. 当当前字符为右括号），那么 3.1. 当lo>0，则lo需要减1，同时，最大个数也减1 3.2. 否则，最大个数减1 即可（例子："∗)"）
4. 当出现hi<0:则说明即使将所有*号替换为左括号，也会出现右括号大于左括号的现象，也就是无效的字符串。 最后，判断lo==0即可。

class Solution {
    public boolean checkValidString(String s) {
        int lo=0;//左括号比右括号多的最少个数，即*变成右括号
        int hi=0;//左括号比右括号多的最大个数，即*变成左括号
        char[] array=s.toCharArray();
        for(char item:array){
            if(item=='('){//左括号时都加一
                lo++;
                hi++;
            }else if(item=='*'){
                if(lo>0){//左括号一定多
                    lo--;
                    hi++;
                }else{//左括号不一定多 
                    hi++;
                }
            }else if(item==')'){//为右括号时
                if(lo>0){//左括号一定多
                    lo--;
                    hi--;
                }else{//左括号不一定多但是当前为右括号减一
                    hi--;
                }
                
            }
            if(hi<0){//*都变成左括号都不够
                return false;
            }
        }

        return lo==0;//判断左括号是否与右括号相等

    }
}

 测试用例

 感悟

题越来越难了！！！