Valid Parenthesis String
You are given a string s which contains only three types of characters: '(', ')' and '*'.
Return true if s is valid, otherwise return false.
A string is valid if it follows all of the following rules:
- Every left parenthesis
'('must have a corresponding right parenthesis')'. - Every right parenthesis
')'must have a corresponding left parenthesis'('. - Left parenthesis
'('must go before the corresponding right parenthesis')'. - A
'*'could be treated as a right parenthesis')'character or a left parenthesis'('character, or as an empty string"".
Example 1:
Input: s = "((**)"
Output: trueExplanation: One of the '*' could be a ')' and the other could be an empty string.
Example 2:
Input: s = "(((*)"
Output: falseExplanation: The string is not valid because there is an extra '(' at the beginning, regardless of the extra '*'.
Constraints:
1 <= s.length <= 100
Recommended Time & Space Complexity
You should aim for a solution as good or better than O(n) time and O(n) space, where n is the length of the input string.
Hint 1
A brute force approach would try all possibilities when encountering a '*' and recursively solve the problem, leading to an exponential approach. Can you think of a better way? Maybe a data structure commonly used in parenthesis problems could be useful.
Hint 2
We can solve the problem using a stack-based approach. We maintain two stacks: one for tracking the indices of left parentheses and another for star indices. As we iterate through the string from left to right, we push indices onto their respective stacks when encountering a left parenthesis '(' or a star '*'. Can you determine the logic for the right parentesis case?
Hint 3
If the left parenthesis stack is not empty, we pop from it. Otherwise, we pop from the star stack, treating the star as a left parenthesis to keep the string valid. After iterating the string, the stacks might be non-empty? Can you determine the logic for this case?
Hint 4
Now, we try to match the remaining left parentheses with stars, ensuring the stars appear after the left parentheses in the string. We simultaneously pop from both stacks, and if the index of a left parenthesis is greater than that of a star, the string is invalid as there is no matching right parenthesis. In this case, we return false.