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.
1import java.util.*;
2
3public class Solution {
4 public String countOfAtoms(String formula) {
5 Map<String, Integer> map = parseFormula(formula, new int[]{0});
6 StringBuilder res = new StringBuilder();
7 for (String name : map.keySet()) {
8 res.append(name);
9 int count = map.get(name);
10 if (count > 1) res.append(count);
11 }
12 return res.toString();
13 }
14
15 private Map<String, Integer> parseFormula(String formula, int[] index) {
16 Map<String, Integer> count = new TreeMap<>();
17 while (index[0] < formula.length()) {
18 char current = formula.charAt(index[0]);
19 if (current == '(') {
20 index[0]++;
21 Map<String, Integer> subMap = parseFormula(formula, index);
22 int multiplier = 1, start = index[0];
23 while (index[0] < formula.length() && Character.isDigit(formula.charAt(index[0]))) {
24 index[0]++;
25 }
26 if (start < index[0]) {
27 multiplier = Integer.parseInt(formula.substring(start, index[0]));
28 }
29 for (String key : subMap.keySet()) {
30 count.put(key, count.getOrDefault(key, 0) + subMap.get(key) * multiplier);
31 }
32 } else if (current == ')') {
33 index[0]++;
34 return count;
35 } else {
36 int start = index[0]++;
37 while (index[0] < formula.length() && Character.isLowerCase(formula.charAt(index[0]))) {
38 index[0]++;
39 }
40 String name = formula.substring(start, index[0]);
41 start = index[0];
42 while (index[0] < formula.length() && Character.isDigit(formula.charAt(index[0]))) {
43 index[0]++;
44 }
45 int multiplicity = (start < index[0]) ? Integer.parseInt(formula.substring(start, index[0])) : 1;
46 count.put(name, count.getOrDefault(name, 0) + multiplicity);
47 }
48 }
49 return count;
50 }
51}
52In Java, we similarly implement a recursive parsing function parseFormula that processes the input formula. A pointer encapsulated in an array is used to track the current index. We utilize a TreeMap for atom counts to automatically order keys alphabetically. The function handles character parsing, and uses recursion to manage the nesting of expressions within parentheses, applying multipliers as needed.
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.
1function countOfAtoms(formula) {
2 let i
We use a stack to handle nested elements in the formula and JavaScript's object to manage atom counts. When encountering a '(', a new object is pushed onto the stack, handling atoms encountered as per usual. On encountering a ')', we pop the object, multiply its counts by the number following the bracket (if any), and merge the result into the object below it on the stack. Finally, the sorted atom counts are used to create the output string.