678. Valid Parenthesis String
Medium
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'*'
.
Runtime: 0 ms, faster than 100%
Memory Usage: 1.8 MB, less than 90.74%
func checkValidString(s string) bool {
if len(s) == 1 && s != "*" { return false }
l, r := 0, 0
for _, c := range s {
if c == '(' || c == '*' {
l++
} else {
l--
}
if l < 0 { return false } // 如果把星星都當成左括號,右括號還大於左括號,勢必不合法
}
if l == 0 { return true } // 左括號+星星變成的左括號剛好和右括號抵銷,合法!
for i:= len(s)-1; i >=0; i-- {
if s[i] == ')' || s[i] == '*' {
r++
} else {
r--
}
if r < 0 { return false }
}
return true
}
Last modified 6mo ago