Number Of Atoms - Leetcode Solution

Problem Statement:

Given a chemical formula (given as a string), return the count of each atom.

An atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

1 or more digits representing the count of that element may follow if the count is greater than 1. If the count is 1, no digits will follow. For example, H2O and H2O2 are possible, but H1O2 is impossible.

Two formulas concatenated together to produce another formula.

Example 1:

Input: formula = "H2O" Output: {"H": 2, "O": 1} Explanation: The count of elements are {"H": 2, "O": 1}.

Example 2:

Input: formula = "Mg(OH)2" Output: {"Mg": 1, "O": 2, "H": 2} Explanation: The count of elements are {"Mg": 1, "O": 2, "H": 2}.

Example 3:

Input: formula = "K4(ON(SO3)2)2" Output: {"K": 4, "O": 14, "N": 2, "S": 4} Explanation: The count of elements are {"K": 4, "O": 14, "N": 2, "S": 4}.

Solution:

The solution to this problem can be solved using a stack and a dictionary. We will traverse the string from left to right and push the characters into the stack. Whenever we encounter an opening bracket ‘(‘, we will push a new dictionary into the stack to collect the counts of the elements in the brackets. Whenever we encounter a closing bracket ‘)’, we will pop the last dictionary from the stack and multiply the element counts by the number outside the brackets.

For example, if we encounter the string ‘Br2(OH4)3’, we will initialize an empty dictionary and push it into the stack. When we encounter the letter ‘B’, we add it to the dictionary. When we encounter the number ‘2’, we update the count of ‘B’ to 2. When we encounter the opening bracket ‘(‘, we push a new empty dictionary into the stack. When we encounter the letter ‘O’, we add it to the second dictionary. When we encounter the letter ‘H’, we add it to the second dictionary. When we encounter the number ‘4’, we update the counts of ‘O’ and ‘H’ to 4. When we encounter the closing bracket ‘)’, we pop the second dictionary from the stack and multiply the counts by the number ‘3’ outside the brackets. We then add the updated counts to the first dictionary.

In the end, we will have the count of each element in the first dictionary.

Python code:

def countOfAtoms(formula: str) -> dict[str, int]: stack = [collections.defaultdict(int)] i = 0 while i < len(formula): c = formula[i] i += 1 if c == '(': stack.append(collections.defaultdict(int)) elif c == ')': count = 0 while i < len(formula) and formula[i].isdigit(): count = count * 10 + int(formula[i]) i += 1 if count == 0: count = 1 last = stack.pop() for elem, cnt in last.items(): stack[-1][elem] += cnt * count else: elem = c while i < len(formula) and formula[i].islower(): elem += formula[i] i += 1 count = 0 while i < len(formula) and formula[i].isdigit(): count = count * 10 + int(formula[i]) i += 1 if count == 0: count = 1 stack[-1][elem] += count return stack[-1]

In this code, we start by initializing a stack with an empty dictionary. We then traverse the string from left to right and use a pointer ‘i’ to keep track of our position. Whenever we encounter an opening bracket, we push a new empty dictionary into the stack. Whenever we encounter a closing bracket, we pop the last dictionary from the stack and multiply the counts by the number outside the brackets. Whenever we encounter a letter, we collect it and any following lowercase letters to form an element name. Whenever we encounter a number, we collect it and multiply the count of the current element. We then add the count to the last dictionary in the stack.

Finally, we return the count of each element in the last dictionary in the stack.

1