Generate Valid Parenthesis Strings from Template
In parsing and compiler design, correctly balanced parentheses are crucial for defining scope and structure. This problem explores the systematic generation of all possible valid parenthesis strings given a template that may contain wildcard characters. This is a fundamental problem that tests a candidate's ability to systematically explore possibilities and manage state, which is critical in many areas from language parsing to configuration validation.
You are given a string template consisting of three types of characters:
'(': An opening parenthesis.')': A closing parenthesis.'?': A wildcard character that can be replaced by either an opening parenthesis '(' or a closing parenthesis ')'.Your task is to generate all unique strings that can be formed by replacing each '?' in the template with either '(' or ')', such that the resulting string is a valid parenthesis string.
A string is considered a valid parenthesis string if:
(()()) is valid, )( is not, (( is not).You should return a list of all such unique valid parenthesis strings. The order of strings in the output list does not matter.
Function Signature:
function generateValidParenthesisStrings(template: string): string[]
template: A string containing '(', ')', and '?'.Return Value:
string[] (array of strings) containing all unique valid parenthesis strings that can be formed from the template."" is considered a valid parenthesis string. If the template is empty, the result should be [""].template will always be the length of the resulting valid strings. Thus, if template.length is odd, no valid parenthesis string can be formed.Examples
Example 1
Input:
template = "(?)"
Output:
[]
Note:
The template has a length of 3. A valid parenthesis string must always have an even length. Since 3 is odd, no valid parenthesis string can be formed from this template.
Example 2
Input:
template = "()"
Output:
["()"]
Note:
The template contains no wildcards. The string "()" is already a valid parenthesis string.
Example 3
Input:
template = "????"
Output:
["(())","()()"]
Note:
For the template "????", two valid parenthesis strings can be formed: "(())" (replacing '?'s with '(( ))' respectively) and "()()" (replacing '?'s with '()()'). The order of the output strings does not matter.
Constraints
1 <= template.length <= 15template string will only contain characters '(', ')', and '?'.Loading editor...