Problem Statement
Correct parentheses sequences can be defined recursively as follows:
- The empty string "" is a correct sequence.
- If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
- If "X" is a correct sequence, then "(X)" is a correct sequence.
- Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".
You are given a
- Remove the first opening parenthesis in s.
- Remove one closing parenthesis in s. After you do so, s must again be a correct parentheses sequence.
Compute and return the number of distinct ways in which s can be reduced to an empty string by performing consecutive removals. Two ways are considered distinct if there is a step in which you remove a different closing parenthesis. (See Example 1 for clarification.) It is guaranteed that the correct return value will always fit into a 32-bit signed integer.
Definition
- Class:
- RemovingParenthesis
- Method:
- countWays
- Parameters:
- String
- Returns:
- int
- Method signature:
- int countWays(String s)
- (be sure your method is public)
Constraints
- s will have between 2 and 20 characters, inclusive.
- s will be a correct parentheses sequence.
Examples
"()()()()()"
Returns: 1
In each removal we have to choose the leftmost closing parenthesis.
"(((())))"
Returns: 24
In each removal we can choose any closing parenthesis we want. Note that these count as distint choices, even though all choices lead to the same string. Thus, there are 4*3*2*1 = 24 different sequences of removals that change s into an empty string.
"((()()()))"
Returns: 54
Below is one of the 54 possible sequences of removals. Remember that in each step we also remove the first opening parenthesis. Remove the fourth closing parenthesis: "(()()())" Remove the second closing parenthesis: "()(())" Remove the first closing parenthesis: "(())" Remove the second closing parenthesis: "()" Remove the first closing parenthesis: ""
"(())(())(())"
Returns: 8
"((()))(()(()))((()))"
Returns: 432
"(((((((((())))))))))"
Returns: 3628800
"()()()()()()()()()()"
Returns: 1
"()"
Returns: 1
"()(())((()))(((())))"
Returns: 288
"()()()(())()()(())"
Returns: 4
"((()((()()))))"
Returns: 1800
"()()()()()(()()()())"
Returns: 16
"()()()()(()()())"
Returns: 8
"()"
Returns: 1
"()()()(())"
Returns: 2
"()()((()()()()))(())"
Returns: 324
"()()()(())()"
Returns: 2
"(())"
Returns: 2
"((()(((())(())))))"
Returns: 64800
"(()(()()())())"
Returns: 216
"()()()()(())"
Returns: 2
"()()()()"
Returns: 1
"()()()()(()())(())"
Returns: 8
"(((()((())()))()))"
Returns: 43200
"((((((()(())))))))"
Returns: 282240
"()()()()()((()))"
Returns: 6
"((((()(())))()))"
Returns: 10800
"()()()()()()()(())"
Returns: 2
"()()()(()())(())(())"
Returns: 16
"()(((()))(((()()))))"
Returns: 14400
"(()(())()((()))())"
Returns: 1152
"((((())((()(()))))))"
Returns: 604800
"(())((()(())(())))"
Returns: 1728
"(((()((())()))))()"
Returns: 14400
"()()()()(())(())"
Returns: 4
"()(())(())(()()())"
Returns: 32
"(())(())(())(()())"
Returns: 32
"((()(())))((())())"
Returns: 864
"()()()()()(())()()"
Returns: 2
"(())()()()(())(())"
Returns: 8
"(((()((())))()))"
Returns: 8640
"()()(())(()()(()))"
Returns: 48
"(((((())))(())))"
Returns: 8640
"()()()()()(())(())"
Returns: 4
"()()()()(()()(()))"
Returns: 24
"()()(())(())()"
Returns: 4
"()()()(())(()())"
Returns: 8
"()()(())(()(())())"
Returns: 48
"()()()()(()()())"
Returns: 8
"(((()((((())))))()))"
Returns: 483840
"((()()()))"
Returns: 54