Leetcode 726: Number of Atoms (IV)

Feb. 1, 2018

Introduction

It is very interesting to read one of discussion and the code is implemented in python. What I like to do is to spend 30 minutes to go over the analysis, and then get the idea how python code works.

What I like to do is to go over the analysis again, and write down the analysis in my own words. Spend more time on the analysis, and then understand the algorithm one thing a time.

Python code

Here is the discussion link.

Study of the blogger

Here is the link I like to study about system design.

Analysis of the algorithm

Regular expression

The first is to understand how to read regular expression, the atom can be expressed in the following expression: ([A-Z]{1}[a-z]?|\\(|\\)|\\d+). I just learned how to write regular expression in 5 minutes.  I documented my practice on algorithm on word count engine algorithm on January 25, 2018 and learn how to write regular expression for delimiters.

The number of atoms

The regular expression can be used to split the input string, and the only four tokens are discussed.  (1) An atom (2) A number (3) Open bracket (4) Closing bracket.

Let us go over a few test case and then how to read them in char array.

An input of Mg(OH)2 will be tokenized into: ['Mg', '(', 'O', 'H', ')', '2'].
An input of K4(ON(SO3)2)2 will be tokenized into: ['K', '4', '(', 'O', 'N', '(', 'S', 'O', '3', ')', '2', ')', '2'].

How to solve the problem?

As we iterate through the tokens, there are three cases that we need to handle:

1. Open bracket - We push a new dictionary onto a stack to keep track of the atoms and its count in this current group.
2. Close bracket - The next token might be a number/count. Check whether if it is a count. If it is, multiply all the atoms at the top of the stack by the count and combine it with a dictionary below it in the stack.
3. Normal atom - The next token might be a number/count. Check whether if it is a count. If it is, add that atom and its count to the top of the stack.

Cases 2 and 3 are very similar, so we can combine them.

At the end, sort the atoms alphabetically and format them nicely to be returned.