Description
Valid Parenthesis String
MediumGiven 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
Example 4:
Input: s = "("
Output: false
Constraints:
1 <= s.length <= 100s[i]is'(',')'or'*'.
Solutions
Double pass solution to guarantee valid ordering.
Language: javascript()DONE
CPU Performance100.00%
x
Memory Performance36.38%
x
/**
* @param {string} s
* @return {boolean}
*/
var checkValidString = function(s) {
let open = 0;
let stars = 0;
for (let i = 0; i < s.length; i++) {
const char = s[i];
if (char === '(') {
open++;
} else if (char === ')' && open > 0) {
open--;
} else if (char === ')' && stars > 0) {
stars--;
} else if (char === '*') {
stars++;
} else {
return false;
}
}
if (open > stars) return false;
open = 0;
stars = 0;
for (let i = s.length - 1; i >= 0; i--) {
const char = s[i];
if (char === ')') {
open++;
} else if (char === '(' && open > 0) {
open--;
} else if (char === '(' && stars > 0) {
stars--;
} else if (char === '*') {
stars++;
} else {
return false;
}
}
return open <= stars;
};