05 August 2008
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.
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}. Example 4:
Input: formula = “Be32” Output: “Be32”
Constraints:
1
2
3
4
1 <= formula.length <= 1000
formula consists of English letters, digits, '(', and ')'.
formula is always valid.
All the values in the output will fit in a 32-bit integer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
// backward scanning + parametrization
// time: O(NlogN) for sorting
// memory: O(N)
private boolean isUpper(char c) {
return c >= 65 && c <= 90;
}
private boolean isLower(char c) {
return c >= 97 && c <= 122;
}
private boolean isDigit(char c) {
return c >= 48 && c <= 57;
}
public String countOfAtoms(String formula) {
int product = 1;
Stack<Integer> mlrStack = new Stack<>();
Map<String, Integer> count = new HashMap<>();
for (int i = formula.length() - 1; i >= 0; --i) {
char c = formula.charAt(i);
// step 0: end of group, update product, skip
if (c == '(') {product /= mlrStack.pop();continue;}
// step 1: scan current multiplier
int rank = 1;
int mlr = 0;
while (isDigit(c)) {// read current multiplier
mlr += rank * (c - 48);
rank *= 10;
c = formula.charAt(--i);
}
if (mlr == 0) {++mlr;}
mlrStack.push(mlr);// update multiplier stack
product *= mlr;// update product
// step 1.5: start of group, skip
if (c == ')') {continue;}
// step 2: scan name of atom
StringBuilder atom = new StringBuilder();
while (isLower(c)) {
atom.insert(0, c);
c = formula.charAt(--i);
}
atom.insert(0, c);
String name = atom.toString();
// step 3: update count of atom
count.put(name, count.getOrDefault(name, 0) + product);
// step z: update product by dividing last multiplier (poped out top from stack)
product /= mlrStack.pop();// update product
}
List<String> atomList = new ArrayList<>(count.keySet());
atomList.sort(Comparator.<String>naturalOrder());
StringBuilder res = new StringBuilder();
for (String atom: atomList) {
res.append(atom);
if (count.get(atom) > 1) {res.append(count.get(atom));}
}
return res.toString();
}
}
O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
class Solution {
/**
* Algorithm
*
*
* 1. When we reach a character that is in uppercase
* - We search it next character to see if it is a lowercase character
* - then we get the element name
* - Next we search if the next character is numeric until we reach a character that isn't
*
*
* 2. The tricky part is parentheses handling
* - When we reach a '('
* We then invoke it self recursively starting from the next index of character and pass
* in a new HashMap for storing sub result inside the parentheses
*
* The recursive function return an ending index when it reach ')'
*
* After the function return, we then search for the character after the ending index
* to see if it numeric until we reach a character that isn't
*
* We then multiply the whole sub result hash map before merging it to the result map
*
*
* - When we reach a ')'
* - we return the index number of it to terminate the recursive call
*
*
*
*/
public String countOfAtoms(String formula) {
//Use TreeMap so that element names are sorted alphabetically
Map<String, Integer> result = new TreeMap<String, Integer>();
countOfAtoms(formula, 0, result);
StringBuilder sb = new StringBuilder();
for(String el : result.keySet()){
sb.append(el);
if(result.get(el) > 1){
sb.append(result.get(el));
}
}
return sb.toString();
}
public int countOfAtoms(String formula, int start, Map<String, Integer> result) {
char c;
int j;
int multiplier;
int endIdx;
int i = start;
for(i=start; i<formula.length(); i++){
c = formula.charAt(i);
if(c == '('){
//Recursive call and pass in a new Map for storing sub result
Map<String, Integer> subResult = new TreeMap<String, Integer>();
i = countOfAtoms(formula, i+1, subResult);
//Scan forward to see if there is a numeric character
multiplier = 1;
endIdx = getMultiplierEndIdx(formula, i+1);
if(endIdx != -1){
//If there is a numeric character, multiply the whole subr esult map
multiplier = Integer.parseInt(formula.substring(i+1, endIdx));
for(String el : subResult.keySet()){
subResult.put(el, subResult.get(el) * multiplier);
}
i = endIdx - 1;
}
//Merging sub result to result
for(String el : subResult.keySet()){
result.put(el, result.getOrDefault(el, 0) + subResult.get(el));
}
}else if(c == ')'){
//Ending recursive call
return i;
}else if(c >= 'A' && c <= 'Z'){
//Scan the element name
endIdx = getElementEndIdx(formula, i);
if(endIdx != -1){
String elName = formula.substring(i, endIdx);
i = endIdx - 1;
multiplier = 1;
//Scan the multiplier
endIdx = getMultiplierEndIdx(formula, i+1);
if(endIdx != -1){
multiplier = Integer.parseInt(formula.substring(i+1, endIdx));
i = endIdx - 1;
}
//Adding count to result
result.put(elName, result.getOrDefault(elName, 0) + multiplier);
}
}
}
return i;
}
/**
* Return end index of a element name
* If startIdx is not a start index of a element name, return -1
*/
private int getElementEndIdx(String formula, int startIdx){
if(startIdx >= formula.length()) return -1;
int j = startIdx;
char c = formula.charAt(j);
if(c < 'A' || c > 'Z') return -1;
j++;
if(j < formula.length()){
c = formula.charAt(j);
if(c >= 'a' && c <= 'z'){
j++;
}
}
return j;
}
/**
* Return multiplier end index so that the caller may use substring to get it
* If multiplier not found, return -1
*/
private int getMultiplierEndIdx(String formula, int startIdx){
if(startIdx >= formula.length()) return -1;
int j = startIdx;
char c = formula.charAt(j);
if(c < '0' || c > '9') return -1;
while(j < formula.length()){
c = formula.charAt(j);
if(c < '0' || c > '9') break;
j++;
}
return j;
}
}