Validate and Balance Parentheses with Wildcards
Given a string s containing only three types of characters: '(', ')', and '*', write a function to check if the string is valid. The validity of a string is determined by these rules:
- Any left parenthesis '(' must have a corresponding right parenthesis ')'.
- Any right parenthesis ')' must have a corresponding left parenthesis '('.
- Left parentheses '(' must appear before their corresponding right parentheses ')'.
- The character '*' can be treated as a single right parenthesis ')', a single left parenthesis '(', or an empty string.
- An empty string is also considered valid.
[ "()" ]
Explanation. Standard balanced parentheses.
[ "(*)" ]
Explanation. The '*' can be treated as an empty string to balance '()'.
[ "(*))" ]
Explanation. The first '*' can be treated as an opening parenthesis '(', making it `(( ))`.
[ "(((" ]
Explanation. Unmatched left parentheses.
[ ")(" ]
Explanation. Right parenthesis appears before a corresponding left parenthesis.
[ "((*)" ]
Explanation. Even if '*' is treated as ')', we are left with an unmatched '('.
[ "(*()*)", "**()**" ]
Explanation. The first '*' can be '(', and the second '*' can be ')' to form `((()()))`.
[ "***" ]
Explanation. All '*' characters can be treated as empty strings.
[ "*" ]
Explanation. The '*' can be treated as an empty string.
[ ")" ]
Explanation. An unmatched right parenthesis.
Follow-up: Can you solve this problem with O(1) space complexity?
- The input string `s` will contain only '(', ')', and '*'. - The length of `s` will be between 1 and 100.
- Views
- 13