動機
Problem
Given a string s
containing only three types of characters: '('
, ')'
and '*'
, return true
if s
is valid.
The following rules define a valid string:
- 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.
Example 1:
Input: s = ()Output: true
Example 2:
Input: s = (*)Output: true
Example 3:
Input: s = (*))Output: true
Constraints:
1 <= s.length <= 100
s[i]
is'('
,')'
or'*'
.
Sol
重點是怎麼處理星號,
- 左括號只能和他之後的星號配對
- 右括號只能和他之前的星號配對
class Solution:
def checkValidString(self, s: str) -> bool:
left = []
star = []
right = []
for i in range(len(s)):
if s[i] == '*':
star.append(i)
elif s[i] == '(':
left.append(i)
else:
if left:
left.pop()
elif star:
star.pop()
else:
right.append(i)
print(left,star,right)
if left:
while left and star and left[-1] < star[-1]:
left.pop()
star.pop()
elif right:
while right and star and star[-1] < right[-1]:
right.pop()
star.pop()
print(left,star,right)
return not left and not right
case study
- 把所有星號當成左括號,去計數,如果左括號太少,就直接False
- 把所有星號當成右括號,去計數,全部跑完,看有沒有被扣完 (多扣沒關係,因為在第一條已經證明左括號+星號一定足夠匹配真正的右括號)
class Solution:
def checkValidString(self, s: str) -> bool:
cmin = cmax = 0
for c in s:
cmax = cmax - 1 if c == ')' else cmax + 1
cmin = cmin + 1 if c == '(' else max(cmin - 1, 0)
if cmax < 0:
return False
return cmin == 0