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
}