[leetcode] 678. Valid Parenthesis String

[leetcode] 678. Valid Parenthesis String

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 s1,star; for(int i=0;istar.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 验证括号字符串​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。