582. Wildcard Brackets
A code editor is cleaning up a line that was damaged during a file transfer. The line s keeps only three kinds of characters: '(', ')' and '*'. Each '*' marks a smudged spot that may be restored as an opening bracket, as a closing bracket, or deleted entirely (every star is decided independently).
A line is balanced when every opening bracket is matched with a later closing bracket, every closing bracket has an earlier opening one, and nothing is left unmatched. An empty line is balanced.
Return true if the smudges can be restored so that the whole line is balanced, otherwise return false. The intended solution runs in O(n) time and O(1) extra space.
Example 1
- Input:
- s = "((*)*"
- Output:
- true
- Explanation:
Reading the first star as nothing and the last star as a closing bracket gives the balanced line (()).
Example 2
- Input:
- s = ")*("
- Output:
- false
- Explanation:
The line starts with a closing bracket and nothing precedes it, so no restoration can balance it.
Example 3
- Input:
- s = "**)(*"
- Output:
- true
- Explanation:
Read the first star as an opening bracket and the second as nothing, then the last star closes the later opening bracket, giving ()().
Constraints
- 1 ≤ s.length ≤ 105
- s[i] is one of
'(',')'or'*'
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)