678. Valid Parenthesis String
Medium
Last updated
Medium
Last updated
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:
Example 2:
Example 3:
Constraints:
1 <= s.length <= 100
s[i]
is '('
, ')'
or '*'
.
Runtime: 0 ms, faster than 100%
Memory Usage: 1.8 MB, less than 90.74%