LeetCode 30 days Challenge - Day 16
本系列将对LeetCode新推出的30天算法挑战进行总结记录,旨在记录学习成果、方便未来查阅,同时望为广大网友提供帮助。
Valid Parenthesis String
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:
1 | Input: "()" |
Example 2:
1 | Input: "(*)" |
Example 3:
1 | Input: "(*))" |
Note:
- The string size will be in the range [1, 100].
Solution
题目要求分析:给定一个包含左右圆括号以及星号的字符串,其中星号可以视为左右圆括号或者空字符串,判断该字符串是否符合规范。
解法:
本题乍一看像栈结构的经典例题,但本题引入了*
号的特殊性,带来了一定难度。
首先考虑,*
的引入带来的影响:
- 假若视为
(
,那么需要一个额外的)
进行匹配。 - 假若视为
)
,那么能额外匹配一个位置在其之前的(
。 - 假若视为空,那么没有影响。
由于一个符合规范的序列,(
往往先于)
出现,因此可以考虑 *
的不同取值,对需要的 )
数量的影响。
假设,最少需要min_num个 )
,最多需要max_num个 )
,问题转化为 *
的不同取值,对上述两个变量的影响:
- 遇到
(
:min_num、max_num都增加1,这是显然的。 - 遇到
)
:- max_num减少1,这也是显然的;
- min_num也减少1,但不少于0(右括号只能匹配其左边的左括号,如果min_num减少成负数,相当于之后的右括号匹配了之前的左括号,是不符合常理的)。
- 遇到
*
:- 因为可以看成一个
(
,max_num增加1; - 也可以看成一个
)
,min_num也减少1,但不少于0(理由同上)。 - 看成空串则不会造成影响。
- 因为可以看成一个
在遍历过程中,若出现max_num小于0的情况,即出现了一个无法匹配的右括号,直接返回 false
。
最后,因为min_num是最少需要的条件,判断min_num是否为0即可。
注:本题较难理解的是min_num在遍历过程中不能小于0的原因:小于0则相当于某一个左括号之后的右括号匹配了该左括号,是不符合常理的,这两个括号就是这种情况“ )( ”。
1 | bool checkValidString(string s) { |
Karl