Approach #1: Recursion [Accepted]

Intuition and Algorithm

Write a function parse that parses the formula from index i, returning a map count from names to multiplicities (the number of times that name is recorded).

We will put i in global state: our parse function increments i throughout any future calls to parse.

• When we see a '(', we will parse whatever is inside the brackets (up to the closing ending bracket) and add it to our count.

• Otherwise, we should see an uppercase character: we will parse the rest of the letters to get the name, and add that (plus the multiplicity if there is one.)

• At the end, if there is a final multiplicity (representing the multiplicity of a bracketed sequence), we'll multiply our answer by this.

Complexity Analysis

• Time Complexity: , where is the length of the formula. It is to parse through the formula, but each of multiplicities after a bracket may increment the count of each name in the formula (inside those brackets), leading to an complexity.

• Space Complexity: . We aren't recording more intermediate information than what is contained in the formula.

Approach #2: Stack [Accepted]

Intuition and Algorithm

Instead of recursion, we can simulate the call stack by using a stack of counts directly.

Complexity Analysis

• Time Complexity , and Space Complexity . The analysis is the same as Approach #1.

Approach #3: Regular Expressions [Accepted]

Intuition and Algorithm

Whenever parsing is involved, we can use regular expressions, a language for defining patterns in text.

Our regular expression will be "([A-Z][a-z]*)(\d*)|($$)|($$)(\d*)". Breaking this down by capture group, this is:

• ([A-Z][a-z]*) Match an uppercase character followed by any number of lowercase characters, then ((\d*)) match any number of digits.
• OR, ($$) match a left bracket or ($$) right bracket, then (\d*) match any number of digits.

Now we can proceed as in Approach #2.

• If we parsed a name and multiplicity ([A-Z][a-z]*)(\d*), we will add it to our current count.

• If we parsed a left bracket, we will append a new count to our stack, representing the nested depth of parentheses.

• If we parsed a right bracket (and possibly another multiplicity), we will multiply our deepest level count, top = stack.pop(), and add those entries to our current count.

Complexity Analysis

• Time Complexity , and Space Complexity . The analysis is the same as Approach #1, as this regular expression did not look backwards when parsing.

Analysis written by: @awice. Approaches #1 and #2 inspired by @zestypanda. Java solution for #3 by @jianchao.li.fighter.