【题目】
给定只包含( ,) 和 *三种字符的字符串,写一个函数来检验是否为有效字符串。有效字符串规则如下:
示例 :
输入: "()"
输出: True
示例 :
输入: "(*)"
输出: True
示例 :
输入: "(*))"
输出: True
注意:
字符串大小将在 [1,100] 范围内。
【思路】
我们可以把'*'当做'('或者')',相当于'('个数不确定。
用low、high分别存储剩余的'('的最少个数(最小为0)和最多个数,因此,low把'*'和')'都视为')',能减则减(大于0的前提下),high把'*'视为'(',遇到'*'自增,遇到')'自减。最后判断low是否为0,返回结果。
具体来说,遍历字符串,当遇到'(',low和high都自增;当遇到')',low>0时才自减,high自减,只要high<0,说明当前右括号数太多,返回False;当遇到'*',low>0时自减,high自增。最后,返回low==0。
【代码】
python版本
class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
if s == '':
return True
# 最少'('个数low,最多'('个数high
low =
high =
for si in s:
if si == '(':
low +=
high +=
elif si == ')':
if low > :
low -=
high -=
if high < :
return False
else:
if low > :
low -=
high +=
return low ==
C++版本
class Solution {
public:
bool checkValidString(string s) {
// 最多左括号个数high,最少左括号个数low
int low=, high=;
char si;
for(int i=; i<s.size(); i++){
si = s[i];
if(si == '('){
low++;
high++;
}else{
if(si == ')'){
if(low > )
low--;
high--;
if(high < )
return false;
}else{
if(low > )
low--;
high++;
}
}
}
return low == ;
}
};