726. Number of Atoms
Problem Explanation
This problem asks to count the number of atoms in a given chemical formula. A chemical formula can consist of a single element with or without a count (e.g. "O" or "O2"), two elements concatenated together (e.g. "H2O"), or a formula placed in parentheses with an optional count (e.g. "(H2O2)" or "(H2O2)3").
The program should break down the formula into its constituent elements and their counts. The output should be a string with each element and its count (if more than 1) in alphabetical order.
For instance, if the input is "H2O", the program should return "H2O" because there are 2 Hydrogen atoms and 1 Oxygen atom. Similarly, if the input is "Mg(OH)2", the program should return "H2MgO2" because there are 2 Hydrogen atoms, 1 Magnesium atom and 2 Oxygen atoms.
Solution Approach
The problem can be proceeded by using recursion and a stack data structure. When we traverse the formula from the left, if we meet an uppercase character, we will parse the rest of the element and add the element and the count to a map. If we meet a '(', we will parse the subformula and multiply the count of all elements in the subformula by the count following the ')'.
Here is how we use recursion and stack. Whenever meet an '(' brace, we create a new stack top and start to trace a new map. When meet a ')' brace, we pop up the map from stack top and merge it into the lower level map. During the process, we need to keep track of the count of each element.
Python Solution
1 2python 3class Solution: 4 def countOfAtoms(self, formula): 5 stack = [collections.Counter()] 6 i = 0 7 8 while i < len(formula): 9 if formula[i] == '(': 10 stack.append(collections.Counter()) 11 i += 1 12 elif formula[i] == ')': 13 top = stack.pop() 14 i += 1 15 start = i 16 while i < len(formula) and formula[i].isdigit(): 17 i += 1 18 multiplier = int(formula[start:i] or 1) 19 for name, v in top.items(): 20 stack[-1][name] += v * multiplier 21 else: 22 start = i 23 i += 1 24 while i < len(formula) and formula[i].islower(): 25 i += 1 26 name = formula[start:i] 27 start = i 28 while i < len(formula) and formula[i].isdigit(): 29 i += 1 30 count = int(formula[start:i] or 1) 31 stack[-1][name] += count 32 33 return "".join(name + (str(stack[-1][name]) if stack[-1][name] > 1 else '') 34 for name in sorted(stack[-1]))
Java Solution
1
2java
3class Solution {
4 public String countOfAtoms(String formula) {
5 int N = formula.length();
6 Stack<Map<String, Integer>> stack = new Stack<>();
7 stack.push(new TreeMap<>());
8
9 for (int i = 0; i < N;) {
10 if (formula.charAt(i) == '(') {
11 stack.push(new TreeMap<>());
12 i++;
13 } else if (formula.charAt(i) == ')') {
14 Map<String, Integer> top = stack.pop();
15 int start = ++i, multiplicity = 1;
16 while (i < N && Character.isDigit(formula.charAt(i))) i++;
17 if (start < i) multiplicity = Integer.parseInt(formula.substring(start, i));
18 for (String c: top.keySet()) {
19 int v = top.get(c);
20 stack.peek().put(c, stack.peek().getOrDefault(c, 0) + v * multiplicity);
21 }
22 } else {
23 int start = i++;
24 while (i < N && Character.isLowerCase(formula.charAt(i))) i++;
25 String name = formula.substring(start, i);
26 start = i;
27 while (i < N && Character.isDigit(formula.charAt(i))) i++;
28 int multiplicity = i > start ? Integer.parseInt(formula.substring(start, i)) : 1;
29 stack.peek().put(name, stack.peek().getOrDefault(name, 0) + multiplicity);
30 }
31 }
32
33 StringBuilder ans = new StringBuilder();
34 for (String name: stack.peek().keySet()) {
35 ans.append(name);
36 int multiplicity = stack.peek().get(name);
37 if (multiplicity > 1) ans.append("" + multiplicity);
38 }
39 return new String(ans);
40 }
41}
Javascript Solution
1 2javascript 3var countOfAtoms = function(formula) { 4 let hash = {}; 5 let i = 0; 6 let count = 1; 7 let stack = []; 8 let name = ""; 9 for (let char of formula) { 10 let code = char.charCodeAt(0); 11 if (65 <= code && code <= 90) { 12 if (name) addName(hash, name, count); 13 name = char; 14 count = 1; 15 } else if (97 <= code && code <= 122) { 16 name += char; 17 } else if ("0" <= char && char <= "9") { 18 count = count * 10 + parseInt(char); 19 } else if (char === "(") { 20 let newObj = {}; 21 stack.push([hash, name, count]); 22 hash = newObj; 23 name = ""; 24 count = 1; 25 } else if (char === ")") { 26 if (name) addName(hash, name, count); 27 let oldHash = stack.pop(); 28 let outsideCount = 0; 29 while (i + 1 < formula.length && "0" <= formula[i + 1] && formula[i + 1] <= "9") { 30 outsideCount = outsideCount * 10 + parseInt(formula[i + 1]); 31 i++; 32 }; 33 if (outsideCount === 0) outsideCount = 1; 34 combine(oldHash[0], hash, name, oldHash[2] * outsideCount); 35 hash = oldHash[0]; 36 name = oldHash[1]; 37 count = 1; 38 } else { // if char == '-' 39 if (name) addName(hash, name, count); 40 count = 1 - parseInt(char); 41 name = ""; 42 }; 43 i++; 44 }; 45 if (name) addName(hash, name, count); 46 47 let result = ""; 48 let sortedKeys = Object.keys(hash).sort((a, b) => a.localeCompare(b)); 49 for (let sortedKey of sortedKeys) { 50 result += sortedKey; 51 if (hash[sortedKey] > 1) result += hash[sortedKey]; 52 }; 53 return result; 54}; 55 56function addName(hash, name, count) { 57 if (hash[name]) { 58 hash[name] += count; 59 } else { 60 hash[name] = count; 61 }; 62}; 63 64function combine(hash, oldHash, name, count) { 65 Object.keys(oldHash).forEach(key => { 66 hash[key] = hash[key] + oldHash[key] * count || oldHash[key] * count; 67 }) 68};
C++ Solution
1 2c++ 3class Solution { 4public: 5 string countOfAtoms(string formula) { 6 int i = 0; 7 map<string, int> counts = parse(formula, i); 8 string ans; 9 for (pair<string, int> p : counts) { 10 ans += p.first; 11 if (p.second > 1) 12 ans += to_string(p.second); 13 } 14 return ans; 15 } 16 17private: 18 map<string, int> parse(string& formula, int& i) { 19 map<string, int> counts; 20 while (i != formula.size() && formula[i] != ')') { 21 if (formula[i] == '(') { 22 i++; // Skip '(' 23 for (auto& p : parse(formula, i)) { counts[p.first] += p.second; } 24 } else { 25 int iStart = i++; 26 while (i != formula.size() && islower(formula[i])) { i++; } 27 string name = formula.substr(iStart, i - iStart); 28 iStart = i; 29 while (i != formula.size() && isdigit(formula[i])) { i++; } 30 int count = iStart == i ? 1 : stoi(formula.substr(iStart, i - iStart)); 31 counts[name] += count; 32 } 33 } 34 int iStart = ++i; 35 while (i != formula.size() && isdigit(formula[i])) { i++; } 36 if (iStart < i) { 37 int multiplicity = stoi(formula.substr(iStart, i - iStart)); 38 for (auto& p : counts) { p.second *= multiplicity; } 39 } 40 return counts; 41 } 42};
C# Solution
1
2csharp
3public class Solution {
4 public string CountOfAtoms(string formula) {
5 int i = 0, len = formula.Length;
6 Stack<Dictionary<string, int>> stack = new Stack<Dictionary<string, int>>();
7 stack.Push(new Dictionary<string, int>());
8 while (i < len) {
9 if (formula[i] == '(') {
10 stack.Push(new Dictionary<string, int>());
11 i++;
12 } else if (formula[i] == ')') {
13 var top = stack.Pop();
14 int start = ++i, num = 1;
15 while (i < len && Char.IsDigit(formula[i])) i++;
16 if (i > start) num = int.Parse(formula.Substring(start, i - start));
17 foreach (var kvp in top)
18 if (stack.Peek().ContainsKey(kvp.Key)) stack.Peek()[kvp.Key] += kvp.Value * num;
19 else stack.Peek().Add(kvp.Key, kvp.Value * num);
20 } else {
21 int start = i++;
22 while (i < len && Char.IsLower(formula[i])) i++;
23 string name = formula.Substring(start, i - start);
24 start = i;
25 while (i < len && Char.IsDigit(formula[i])) i++;
26 int num = i > start ? int.Parse(formula.Substring(start, i - start)) : 1;
27 if (stack.Peek().ContainsKey(name)) stack.Peek()[name] += num;
28 else stack.Peek().Add(name, num);
29 }
30 }
31 var sb = new StringBuilder();
32 var list = stack.Peek().Keys.ToList();
33 list.Sort();
34 foreach (string c in list)
35 sb.Append(c + (stack.Peek()[c] > 1 ? stack.Peek()[c].ToString() : ""));
36 return sb.ToString();
37 }
38}
All these solutions involved employing a stack data structure for handling parentheses and a map for keeping storing the count of the elements. The stack would keep track of the corresponding map that contains the element and its count. If the program encounters an open parentheses or an upper case alphabet that signifies the beginning of a chemical symbol, it either begins by creating a new map or extracts the chemical symbol and its count and stores them into the map. For any closing parentheses, it intelligently reflects the multiplication factor (if any) associated with the chemical compounds enclosed by the parentheses on the corresponding counts, and merges them into a single map.
Any programming language with built-in or library-supported data structures like stack and map like Python, Java, JavaScript, C++ and C# can solve this problem with a similar approach. The differences lie in the syntax, and the way built-in methods are used. The Java solution, for instance, uses the 'peek()' function of the Stack data structure, which is used to look at the top element of the stack without deleting it. The JavaScript solution, on the other hand, extracts the character codes to determine whether a character is uppercase, lowercase, or a number. The C++ solution uses a map instead of counter to track each atom and its counts.
When choosing a language to solve this problem, consider the language’s syntax, available libraries, and runtime performance. For example, Python's collections library provides a Counter class which makes counting convenient, while Java's Stack class provides built-in methods like peek(), push() and pop() which lessen the programmer’s job. JavaScript to determine a character's type by extracting the character code using 'charCodeAt' function which is neat. The performance may also be an important factor as Java and C++ tend to outperform Python and JavaScript in large-scale data manipulation. Evaluating features provided by different languages can guide you to pick the most suitable language for different problems.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorA person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.