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
}