HàPhan 河

Valid Parenthesis String

Given a string containing only three types of characters: `(`, `)` and `*`, write a function to check whether this string is valid. We define the validity of a string by these rules:

1. Any left parenthesis `(` must have a corresponding right parenthesis `)`.
2. Any right parenthesis `)` must have a corresponding left parenthesis `(`.
3. Left parenthesis `(` must go before the corresponding right parenthesis `)`.
4. `*` could be treated as a single right parenthesis `)` or a single left parenthesis `(` or an empty string.
5. An empty string is also valid.

Example 1:

``````Input: "()"
Output: True
``````

Example 2:

``````Input: "(*)"
Output: True
``````

Example 3:

``````Input: "(*))"
Output: True
``````

Note:
The string size will be in the range [1, 100].

Solution

Use two counter when, meet "(" increase, meet ")" decrease.
First counter assume "*" is "("
Second counter assume "*" is ")"

``````class Solution {
func checkValidString(_ s: String) -> Bool {
var assumeLeft = 0
var assumeRight = 0

for c in s {
switch c {
case "(":
assumeLeft += 1
assumeRight += 1
case ")":
if assumeLeft > 0 { assumeLeft -= 1 }
assumeRight -= 1
case "*":
if assumeLeft > 0 { assumeLeft -= 1 }
assumeRight += 1

default: break
}

if assumeRight < 0 { return false }
}

return assumeLeft == 0
}
}
``````