题目
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
- 任何左括号 ( 必须有相应的右括号 )。
- 任何右括号 ) 必须有相应的左括号 ( 。
- 左括号 ( 必须在对应的右括号之前 )。
- *可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。
思路
-
这道题我一直没写对，难受死了，最后发现是考虑漏了情况。
-
我最开始的思路是，统计左括号，然后t++；统计右括号，t–;额外统计*号。
-
这个思路里最核心的一步就是从左右到右遍历的过程里，不允许右括号远远大于左括号，以至于即使用*替换也无法补救。
-
现在来看，思路其实是没错的，但为啥一直写不出来，其实就是只考虑了从左到右的过程，没考虑从右到左的过程，也是不允许左括号远远大于右括号，以至于用*号代替也无法补救。
-
因此，最后的思路，就是从左到右写个循环，约束一下；然后再从右到左写个循环，再约束一下，得到最终结果。
-
另外，别跟我一样，硬想，也可以参考其他题解，吸收了就是自己的，我就是因为假期在家就不考虑时间，也考虑效率，结果花了一下午时间。
代码
class Solution {
public static boolean checkValidString(String s) {
int n = s.length() ;
char[] a=s.toCharArray();
int cnt = 0, cnt2 = 0 ;
for(int i = 0 ; i < n ; ++ i)
{
if(a[i] == '*') {
cnt2 ++ ;
} else if(a[i] == '(') {
cnt ++ ;
} else
{
cnt -- ;
if(cnt < 0)
{
if(cnt2 == 0)
{
return false ;
}
cnt2 -- ;
cnt ++ ;
}
}
}
cnt = cnt2 = 0 ;
for(int i = n-1; i >= 0 ; -- i)
{
if(a[i] == '*') {
cnt2 ++ ;
} else if(a[i] == ')') {
cnt ++ ;
} else
{
cnt -- ;
if(cnt < 0)
{
if(cnt2 == 0)
{
return false ;
}
cnt2 -- ;
cnt ++ ;
}
}
}
return true ;
}
}