Digit-Deleted Parentheses
HardDynamic Programming ยท Google
Given a string s of (, ) and digits 1 to 9, return whether the digits can delete parentheses so that what remains is balanced.
Digits act from left to right. A digit d must delete exactly d parentheses that appear before it and are not yet deleted, and you choose which ones. If fewer than d are available, return False. Digits are never deleted and are ignored in the final string.
The remaining parentheses, in their original order, are balanced if every prefix has at least as many ( as ) and the totals are equal. An empty result is balanced.
Example 1
- Input:
- s = "(()1"
- Output:
- True
- Explanation
- The digit deletes one of the three parentheses; deleting either
(leaves().
Example 2
- Input:
- s = "(1))"
- Output:
- False
- Explanation
- The digit can only delete the
(before it, which leaves)).
Example 3
- Input:
- s = "(((1))11"
- Output:
- True
Constraints
0 <= s.length <= 4000scontains only(,)and the digits1to9- A digit may appear anywhere, including at the start of
s