FunctionRacerProblemsRace

Fill In the Brackets

MediumRecursionPython, JavaScript, TypeScript, Java, C++

pattern is made of the characters (, ) and ?. Replace every ? with either ( or ) so that the brackets of the result are balanced: reading from left to right, the number of ) read so far never exceeds the number of ( read so far, and at the end the two numbers are equal. The brackets already in pattern stay as they are.

Return every balanced result, sorted in plain string order, in which ( comes before ). If no choice of replacements gives a balanced result, return an empty list. An empty pattern is already balanced, so it gives [""], and a pattern with no ? gives a list holding just itself when it is balanced and [] when it is not.

A recursive function that places one character at a time and keeps count of the brackets still open is the natural fit. A loop over a list of partial results works too.

Example 1

pattern "(???"
returns ["(())","()()"]

The first bracket is fixed as (; the three question marks can become ()) or )(), giving (()) and ()().

Example 2

pattern "??????"
returns ["((()))","(()())","(())()","()(())","()()()"]

Six question marks can make all five balanced strings with three pairs of brackets, listed in sorted order.

Example 3

pattern "?("
returns []

The string ends with (, which can never be closed, so no replacement works.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Recursion problems