Description
Given a string containing only three types of characters: ‘(’, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:
Any left parenthesis ‘(’ must have a corresponding right parenthesis ‘)’.
Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(’.
Left parenthesis ‘(’ must go before the corresponding right parenthesis ‘)’.
‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(’ or an empty string.
An empty string is also valid.
Example 1:
Input:
"()"
Output:
True
Example 2:
Input:
"(*)"
Output:
True
Example 3:
Input:
"(*))"
Output:
True
Note:
- The string size will be in the range [1, 100].
分析
題目的意思是:驗證一個字元串是否是合法字元串。
- 這道題目我想到用了棧,但是沒想到棧存放的是索引,在最後用來判斷“*”能否消去s1裡面的做括号,如果star的索引比s1的小,說明就不能當成右括号使用,直接傳回false。
代碼
class Solution {
public:
bool checkValidString(string s) {
stack<int> s1,star;
for(int i=0;i<s.length();i++){
if(s[i]=='('){
s1.push(i);
}else if(s[i]==')'){
if(s1.empty()&&star.empty()){
return false;
}
if(s1.empty()&&!star.empty()){
star.pop();
}else{
s1.pop();
}
}else{
star.push(i);
}
}
while(!s1.empty()&&!star.empty()){
if(s1.top()>star.top()){
return false;
}
star.pop();
s1.pop();
}
return s1.empty();
}
};
代碼二(python)
- 設兩個變量l和h,l最少左括号的情況,h表示最多左括号的情況,其它情況在[l, h]之間。
- 周遊字元串,遇到左括号時,l和h都自增1;當遇到右括号時,當l大于0時,l才自減1,否則保持為0(因為其它*情況可能會平衡掉),而h減1;
- 當遇到星号時,當l大于0時,l才自減1(當作右括号),而h自增1(當作左括号)。如果h小于0,說明到此字元時前面的右括号太多,有*也無法平衡掉,傳回false。
- 當循環結束後,傳回l是否為0。
class Solution:
def checkValidString(self, s: str) -> bool:
l=0
h=0
for ch in s:
if(ch=='('):
l+=1
h+=1
elif(ch==')'):
if(l>0):
l-=1
h-=1
else:
if(l>0):
l-=1
h+=1
if(h<0):
return False
return l==0
參考文獻
[LeetCode] Valid Parenthesis String 驗證括号字元串
[LeetCode] 678. Valid Parenthesis String 驗證括号字元串