Brackets With Wildcards

Medium

You are given a pattern pattern made of the characters (, ) and *. Each star must, independently, become (, become ), or be deleted. Return True if the stars can be chosen so that the result is a balanced bracket sequence: every opening bracket has a matching closing bracket to its right, and every closing bracket has a matching opening bracket to its left. The empty string counts as balanced.

Example 1

pattern='(*))' → True

Turn the * into ( and you get "(())".

Example 2

pattern=')*(' → False

The first ) closes something that was never opened, and no choice for the * to its right can fix that.

Example 3

pattern='*' → True

The star can simply vanish, and the empty string is balanced.

Constraints

1 ≤ pattern.length ≤ 100
pattern[i] is (, ) or *

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy String Dynamic Programming

Similar problems

Fill In to Repeated abc Medium Every Letter Once Medium Erase Digits for the Smallest Number Medium Smallest Up-Down Sequence Medium Brackets to Patch In Medium

Input

pattern='(*))'

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 184 tests on the server, hidden ones included.