※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: 678. Valid Parenthesis String
: 给你一个只包含 "(",")","*" 的字串s，"*" 可以是左括号、右括号或空字串，求出s是
: 否可以组成一个合法的括号表达式。
思路：
差不多
用两个stack分别记录左括号和*的位置
遇到右括号优先找有没有左括号，没有再去找有没有*
如果都没有就回传false
遍历完s后会有两种可能
1.还有多的左括号
2.没有多的左括号
没有左括号的话就可以直接回传true了
还有多的左括号，就要去看有没有*的位置在左括号的右边
就这样一直判断到左括号的stack清空为止
golang code:
func checkValidString(s string) bool {
stack:=[]int{}
rec:=[]int{}
for key,val:=range s{
if val=='('{
stack=append(stack,key)
}else if val==')'{
if len(stack)>0{
stack=stack[:len(stack)-1]
}else if len(rec)>0{
rec=rec[:len(rec)-1]
}else{
return false
}
}else{
rec=append(rec,key)
}
}
if len(stack)>len(rec){
return false
}
for len(stack)>0{
if stack[len(stack)-1]>rec[len(rec)-1]{
return false
}else{
stack=stack[:len(stack)-1]
rec=rec[:len(rec)-1]
}
}
return true
}