Solution to leetcode problem 856: Score of parentheses

In this Leetcode problem, we are given a balance parentheses string. That roughly means that each opening parenthesis is matched with exactly one closing parenthesis placed after the opening parenthesis. This way we won’t have illegal strings such as ()) or )(())(.

We are given a recursive definition of String score:

• score( () ) = 1 (base case)
• score( (A) ) = 2 * score( A )
• score( AB ) = score( A ) + score( B )

The first observation to do with balance parentheses strings. They can be represented better by trees. The key is to see that a matching pair of parentheses represent a tree and all parentheses between these 2 represent all the children. Also, not that the string() would be represented by a leaf.

( (child A) (child B) (child C) ) is represented by the tree:

Tree representation of parentheses string

For instance, example 4 of the problem is "(()(()))" can be represented that way:

Tree representation of parentheses string example

For scoring, we would just need to combine the two last rules, and the score of ( A B C) becomes 2 * (score(A) + score(B) + score(C)). Here is how the score would be calculated for the example tree:

Scoring of a tree

We also notice that the string can represent many trees instead of just one. For instance (())(()) represent 2 trees in our definition, so we create a root to contain all of these trees as children. The scoring is a little different for this root that we created, as we add the scores of all the children, but we don’t multiply by 2 this time.

In summary, the algorithm I used has 2 parts. First, I build the tree representation of the problem. Then I compute the score recursivley using the definition.

public int scoreOfParentheses(String S) {…