Given a string formula representing a chemical formula, return the count of each atom.
The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.
One or more digits representing that element’s count 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 are concatenated together to produce another formula.
- For example,
"H2O2He3Mg4"is also a formula.
A formula placed in parentheses, and a count (optionally added) is also a formula.
- For example,
"(H2O2)"and"(H2O2)3"are formulas.
Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.
The test cases are generated so that all the values in the output fit in a 32-bit integer.
Example 1:
Input: formula = "H2O"
Output: "H2O"
Explanation: The count of elements are {'H': 2, 'O': 1}.
Example 2:
Input: formula = "Mg(OH)2"
Output: "H2MgO2"
Explanation: The count of elements are {'H': 2, 'Mg': 1, 'O': 2}.
Example 3:
Input: formula = "K4(ON(SO3)2)2"
Output: "K4N2O14S4"
Explanation: The count of elements are {'K': 4, 'N': 2, 'O': 14, 'S': 4}.
Constraints:
1 <= formula.length <= 1000formulaconsists of English letters, digits,'(', and')'.formulais always valid.
Approach 01
-
C++
-
Python
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string countOfAtoms(string formula) {
string result;
int index = 0;
// Parse the formula and build the result string
for (const auto& [element, frequency] : parse(formula, index)) {
result += element;
if (frequency > 1)
result += to_string(frequency);
}
return result;
}
private:
// Parse the formula and return a map of elements with their frequencies
map<string, int> parse(const string& formula, int& index) {
map<string, int> elementCount;
while (index < formula.length()) {
if (formula[index] == '(') {
// If we encounter '(', we parse the inside and merge the
// results
for (const auto& [element, frequency] : parse(formula, ++index))
elementCount[element] += frequency;
} else if (formula[index] == ')') {
// If we encounter ')', we get the multiplier and return the
// count
const int multiplier = getNumber(formula, ++index);
for (auto&& [_, frequency] : elementCount)
frequency *= multiplier;
return elementCount; // Return back to the previous scope.
} else { // If it's an element, parse it and its frequency
const string& element = getElement(formula, index);
const int frequency = getNumber(formula, index);
elementCount[element] += frequency;
}
}
return elementCount;
}
// Get the element name starting from index
string getElement(const string& formula, int& index) {
const int elementStart =
index++; // `formula[elementStart]` is uppercased.
while (index < formula.length() && islower(formula[index]))
++index;
return formula.substr(elementStart, index - elementStart);
}
// Get the number following an element or parenthesis starting from index
int getNumber(const string& formula, int& index) {
const int numberStart = index;
while (index < formula.length() && isdigit(formula[index]))
++index;
const string& numberString =
formula.substr(numberStart, index - numberStart);
return numberString.empty() ? 1 : stoi(numberString);
}
};
class Solution:
def countOfAtoms(self, formula: str) -> str:
index = 0
# Parse the formula and build the result string
element_count, _ = self.parse(formula, index)
result = ''
for element, frequency in sorted(element_count.items()):
result += element
if frequency > 1:
result += str(frequency)
return result
def parse(self, formula: str, index: int) -> tuple:
element_count = {}
while index < len(formula):
if formula[index] == '(':
# If we encounter '(', we parse the inside and merge the results
index += 1
nested_count, index = self.parse(formula, index)
for element, frequency in nested_count.items():
element_count[element] = element_count.get(element, 0) + frequency
elif formula[index] == ')':
# If we encounter ')', we get the multiplier and return the count
index += 1
multiplier, index = self.get_number(formula, index)
for element in element_count:
element_count[element] *= multiplier
return element_count, index # Return back to the previous scope.
else:
# If it's an element, parse it and its frequency
element, index = self.get_element(formula, index)
frequency, index = self.get_number(formula, index)
element_count[element] = element_count.get(element, 0) + frequency
return element_count, index
def get_element(self, formula: str, index: int) -> tuple:
element_start = index # `formula[element_start]` is uppercased.
index += 1
while index < len(formula) and formula[index].islower():
index += 1
return formula[element_start:index], index
def get_number(self, formula: str, index: int) -> tuple:
number_start = index
while index < len(formula) and formula[index].isdigit():
index += 1
number_string = formula[number_start:index]
return (int(number_string) if number_string else 1), index
Time Complexity
- Parsing the Formula:
The algorithm parses the formula character by character, and each character is processed a constant number of times, leading to a time complexity of \( O(n) \), where \( n \) is the length of the formula.
- Handling Nested Parentheses:
Since the algorithm uses recursion to handle nested parentheses, the complexity remains \( O(n) \) as each character is still processed a constant number of times.
- Overall Time Complexity:
The overall time complexity is \( O(n) \).
Space Complexity
- Auxiliary Space:
The algorithm uses additional space for the recursion stack in the worst case (when parentheses are deeply nested) and the map to store element counts. This results in \( O(n) \) space usage.
- Overall Space Complexity:
The overall space complexity is \( O(n) \).