Flexible brackets: hints, no solution
Medium · Greedy
A shipping manifest marks each pallet group with '(' at its start and ')' at its end. Some marks are smudged and appear as '*', and a smudged mark may really have been an opening mark, a closing mark or nothing at all, whichever you need. Decide whether the manifest can be read as balanced: every opening mark is matched by a later closing mark, no closing mark comes before its opening mark, and none is left unmatched. Return true if some reading of the smudged marks makes it balanced, otherwise false. An empty manifest is balanced.
Examples
- Input
- manifest = "(*))"
- Output
- true
- Note
- Read the star as an opening mark to get (()), which is balanced.
- Input
- manifest = "*("
- Output
- false
- Note
- The final opening mark has nothing after it to close it.
- Input
- manifest = ")*("
- Output
- false
Constraints
- 0 <= manifest.length <= 400000
- Each character is '(', ')' or '*'
Hint 1: a nudge
Try reading the manifest from left to right and asking how many opening marks could be waiting at this point. Is it a single number or a range of numbers?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.