Sponsored
Sponsored
This approach uses a recursive parsing strategy combined with a stack to handle the nested nature of formulas within parenthesis. When encountering a parenthesis, we call the function recursively to process the sub-formula, using the stack to apply multipliers correctly once recursion unwinds back to the outer level.
Time Complexity: O(n), where n is the length of the formula, since we parse through each character once.
Space Complexity: O(n), due to the recursion stack and the storage of atom counts.
1from collections import defaultdict
2
3def count_of_atoms(formula: str) -> str:
4 def parse_formula(index):
5 count = defaultdict(int)
6 while index < len(formula):
7 if formula[index] == '(':
8 sub_count, index = parse_formula(index + 1)
9 multiplier = 1
10 start = index
11 while index < len(formula) and formula[index].isdigit():
12 index += 1
13 if index > start:
14 multiplier = int(formula[start:index])
15 for atom in sub_count:
16 count[atom] += sub_count[atom] * multiplier
17 elif formula[index] == ')':
18 return count, index + 1
19 else:
20 i = index
21 index += 1
22 while index < len(formula) and formula[index].islower():
23 index += 1
24 atom = formula[i:index]
25 start = index
26 while index < len(formula) and formula[index].isdigit():
27 index += 1
28 multiplicity = int(formula[start:index] or 1)
29 count[atom] += multiplicity
30 return count, index
31
32 total_count, _ = parse_formula(0)
33 sorted_atoms = sorted(total_count.keys())
34 return ''.join([f"{atom}{total_count[atom] if total_count[atom] > 1 else ''}" for atom in sorted_atoms])
35We create a recursive function parse_formula that tracks the current index in the formula. We loop through characters, processing each segment as either an atom, number, opening parenthesis, or closing parenthesis. For each atom or sub-formula, we determine its count and add it to a dictionary, which accumulates the counts of each atom in the current context. When encountering a closing parenthesis, we return from the recursion with the accumulated counts for that segment to be multiplied accordingly. Finally, the main function uses a sorted list of atoms for output formatting.
This approach leverages an iterative stack-based strategy to process the formula without recursion. By using an explicit stack, the nested structure is managed more explicitly by keeping track of counts at each level of parentheses, applying multipliers when unwinding back.
Time Complexity: O(n), traversing through the formula.
Space Complexity: O(n), due to the stack's and map's memory usage.
1#include <iostream>
2#include <map>
3#include <stack>
4#include <string>
5#include <cctype>
6using namespace std;
string countOfAtoms(string formula) {
stack<map<string, int>> stk;
map<string, int> current_map;
int i = 0;
while (i < formula.length()) {
if (formula[i] == '(') {
stk.push(current_map);
current_map.clear();
i++;
} else if (formula[i] == ')') {
i++;
int start = i, multiplicity = 1;
while (i < formula.length() && isdigit(formula[i])) i++;
if (start < i) multiplicity = stoi(formula.substr(start, i - start));
if (!stk.empty()) {
map<string, int> temp_map = current_map;
current_map = stk.top();
stk.pop();
for (auto &pair : temp_map) {
current_map[pair.first] += pair.second * multiplicity;
}
}
} else {
int start = i++;
while (i < formula.length() && islower(formula[i])) i++;
string atom = formula.substr(start, i - start);
start = i;
while (i < formula.length() && isdigit(formula[i])) i++;
int multiplicity = (start < i) ? stoi(formula.substr(start, i - start)) : 1;
current_map[atom] += multiplicity;
}
}
string result;
for (auto &pair : current_map) {
result += pair.first + (pair.second > 1 ? to_string(pair.second) : "");
}
return result;
}
int main() {
string formula = "Mg(OH)2";
cout << countOfAtoms(formula) << endl;
return 0;
}
This C++ solution uses an iterative approach with a stack to manage ongoing calculations and resolve nested parentheses structures. A map is maintained for the current level of parsing, storing atom counts and using a stack to save the state when entering new parentheses. On encountering a closing parenthesis, values are multiplied and merged back into the previous level. The std::map is employed for automatic alphabetical ordering of keys.