很全面的一道题目；
三种思路，卡在了索引上，没有悟出来记录左括号索引和星号索引；
1.栈版本：之前想的是判断左括号，压栈，利用变量记录星号，并且优先弹左括号；
但是这样子做会失去星号变成右括号是否可行；
例如"***((("和“(((***”的内容一样，必须要额外记录；
因此采用两个栈，全部记录索引，一个记录左括号，一个记录星号；
最后如果剩下左括号，则说明需要用星号充当右括号；
依次弹出左括号，只需要保证有星号在其右边就行；
2.计数版本：和之前的一个非栈版本括号匹配类似，利用left来记录可以匹配的左括号；
由于星号可以充当左括号，则可以分为俩个情况：
- 充当，记录为lmax；
- 不充当，记录为lmin；
因此极端不能匹配情况为，右括号太多，左括号和星号加起来都不能匹配，此时必有lmax为负数；
而随着匹配到右括号，lmax和lmin都应该减一，此时lmin有可能是负的；
但是负值不影响，之所以是负值是因为右括号太多，此时需要星号来对冲，只要lmax不为负就满足条件；
所以lmin如果为0直接判定为0；
最后判断lmin是否为0，如果不为0，则说明左括号过多，无法完成匹配；
3.DP版本：复杂度有点高，按照题解的版本，首先判断第i和第j位是否满足要求，如果满足且i+1~j-1也满足，为true；
但是要从中介切割，分为两段判定；
例如：
“()()”；
i=0,j=3的时候虽然i=1和j=2构不成满足要求的段；
但是以1为分界点，0～1，2～3可以满足；
所以dp转移方程为：
for (int k = i; k < j && !dp[i][j]; k++) {
dp[i][j] = dp[i][k] && dp[k + 1][j];
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/valid-parenthesis-string/solution/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
基本算法：
1.栈版本：
class Solution {
public:
bool checkValidString(string s) {
stackstl;
stacksts;
for(int i=0;i
if(s[i]=='*'){
sts.push(i);
continue;
}
if(s[i]=='('){
stl.push(i);
continue;
}
if(stl.empty()&&sts.empty())
return false;
if(!stl.empty()){
stl.pop();
}else{
sts.pop();
}
}
while(!stl.empty()){
int index=stl.top();
if(sts.empty()||sts.top()
2.标识记录版本：
class Solution {
public:
bool checkValidString(string s) {
int maxl=0,minl=0;
for(auto& ch:s){
if(ch=='('){
maxl++;
minl++;
}else if(ch=='*'){
minl=max(0,minl-1);
maxl++;
}else{
maxl--;
if(maxl<0){
return false;
}
minl=max(0,minl-1);
}
}
return minl==0;
}
};
3.DP版本： 
