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'*'
.
Solution:
class Solution {
/**
* @param String $s
* @return Boolean
*/
function checkValidString($s) {
$lower = 0;
$upper = 0;
for ($i = 0; $i < strlen($s); $i++) {
$lower += ($s[$i] == '(') ? 1 : -1;
$upper -= ($s[$i] == ')') ? 1 : -1;
if ($upper < 0) break;
$lower = max($lower, 0);
}
return $lower == 0;
}
}
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!