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 <= 100s[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