作者 | 戴助教+本助教
编辑 | Cecily
专栏 | 九章算法
给定一个字符串，由（ * ）三个字符组成，判断是否满足要求左括号和有括号一一对应，且对应的左括号必定在右括号前面。其中，*可以被当做一个单独的左括号，右括号或者可以当做不存在
1.
Input
: "()"
Output
: True
2.
Input
: "(*)"
Output
: True //*被当做空字符，不存在
3.
Input
: "(*))"
Output
: True //星号被当做左括号
首先进行最基础的考虑，（在不考虑星号的情况下）我们必定会选择位置最接近的左右括号配对，这样避免了人为造成的右括号前面没有左括号匹配的惨剧。因此我们在写程序进行处理的时候，对于每个右括号判断前面是否有1个左括号能被他拥有，如果左括号数量不足，这个字符串必定是false，或者当整个串被匹配完之后发现有多余的左括号，这个字符串同样是false
接下来考虑有星号的情况:”)”必须由位置在它之前的”(”或”*”匹配，如果”(”或者”*”数量不足导致的false是无法避免的，而如果”(“ 比”）”多，将”(”与”*”优先匹配可以减小false的可能性。举个例子如样例3，从左往右遍历的时候，优先匹配”（”和”*”，遇见第一个”)”，发现没有单独的”(”,从”(*”的组合中拆出一个”(“与之匹配，而原先匹配中的*因为可以等同于不存在便不予理会，接着遇到第二个”)”,拿走刚才剩余的”*”。综上我们可以观察到，”(”容易受制于”)”而将其与”*”匹配后就很灵活，不仅避免了数量太多带来的麻烦，也能在和*匹配后再次提供自身给”)”进行匹配。而如果这样匹配结束还有多余的”(”则必定false
我们设l（left）为必须被右括号匹配的左括号数量，cp（couple）为前面左括号和星号数量。遍历字符串，遇到左括号和星号的时候,cp++; 遇到右括号的时候cp—; 遇到星号，默认先于前面的左括号(l>0)匹配,此时(l—)，遇到右括号，默认先与前面必须与右括号匹配的左括号匹配，此时(l—;cp—;)或者在
支援兵
中考虑(cp—) 注意cp是前方左右的左括号和星号数量，一旦cp<0即false. 匹配完发现(l>0)即多出了左括号，也为false。剩下的情况就是true了
http://www.jiuzhang.com/solution/valid-parenthesis-string/
http://www.jiuzhang.com/solutions/valid-parentheses
-
回复“简历”，查看简历撰写指南，获取“简历模板”
-
回复“冷冻期”，查看北美各大IT企业冷冻期信息和注意事项
-
回复“Career”, 查看Caireer Fair 攻略 check list
-
回复“薪资”，查看北美各大IT企业New Grades Engineer 薪资水平；
-
回复“项目”，查看7-14天可以搞定的小项目推荐
-
回复“评分”，查看系统设计评分指南
-
回复“behavior”，查看behavior interview指南
-
回复“晋升”，查看Engineer晋升机制
