Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.
The following rules define a valid string:
'(' must have a corresponding right parenthesis ')'.')' must have a corresponding 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 <= 100s[i] is '(', ')' or '*'.In this approach, we use two stacks. One stack will store indices of '(' characters, and the other will store indices of '*' characters as we traverse the string.
If we find a ')' character and there are unmatched '(' in the stack, we pop one out as it can be matched. If no '(' is available, we match using '*'. After processing, all unmatched '(' should be balanced by '*' appearing after them in the string.
The function uses two stacks to keep track of the positions of '(' and '*' characters. When encountering ')', it attempts to match it using an available '(' or '*'. After scanning the string, any remaining unmatched '(' is checked against '*' to ensure validity.
JavaScript
Time Complexity: O(n), as we process each character of the string once.
Space Complexity: O(n), due to use of two stacks to track indices of '(' and '*'.
This approach involves maintaining two balance counts: one for keeping a minimal balance and the other for maximal considering '*' as both '(' and ')'.
As we traverse, the minimal balance ensures ')' never exceeds '(' without the aid of '*', while the maximal balance accounts for replacing '*' with '('. If at any point the maximal balance is negative, then parentheses can't be balanced.
The C++ solution uses two balance counters. It iterates over the string adjusting minBal and maxBal based on the character encountered ('(', ')', or '*'). The maxBal ensures we never have more ')' than possible '('. Negative minBal is reset to reflect reality where '*' can become '(' or empty.
C#
Time Complexity: O(n), as we traverse the string once.
Space Complexity: O(1), since we use a constant amount of extra space regardless of the input size.
| Approach | Complexity |
|---|---|
| Stack-based Approach | Time Complexity: O(n), as we process each character of the string once. |
| Greedy Approach with Balances | Time Complexity: O(n), as we traverse the string once. |
Valid Parentheses - Stack - Leetcode 20 - Python • NeetCode • 475,216 views views
Watch 9 more video solutions →Practice Valid Parenthesis String with our built-in code editor and test cases.
Practice on FleetCode