Problem Description
Give a chemical formula, return the count of each atom.
- The count after atom only writes if it’s more than 1
- A formula placed in parentheses, and a count after the right parenthesis(maybe not) is also a formula:
(H2O2)
,(H2O)2
- The atom in the returned string should in lexicographic order
Example:
Input: formula = "Mg(OH)2"
Output: "H2MgO2"
Problem Analysis
It is obvious that the difficulty in this problem is to remove the parentheses.
Each atom inside a parentheses, needs to multiple the count outside the parentheses. Because the number of atoms in this parentheses needs to be multipled by, and each atom has its corresponding count. So we can abstract the content inside each parentheses as a map.
So an outer parentheses may contains may inner parentheses inside: (Fe2(SO4)3)2
, so we can regard the inner parentheses part SO4
as a innerMap
, the outer Fe2(innerMap)3
as the outer map.
We can go through from left to right
- If comes a
(
, then we create a new inner map - If comes an atom, then we record its number in the inner map
- If comes a
)
, then we open the inner map, multiple each atom number with the number comes after)
(if no number following, just multiple 1). And finally, merge the multipled inner map to the outer map.
And the outer map multipled and merge to the outer’s outer map, and etc.
So we can use a stack whose elements are maps to solve this problem.
String formula;
int idx, len;
public String countOfAtoms(String fml) {
this.formula = fml; // the chemical formula
this.idx = 0; // the index we are handling
this.len = formula.length();
// create the map stack
Deque> stack = new ArrayDeque<>();
// default map containing atoms outside any parentheses, eg:Fe
in Fe2(SO4)3
stack.push(new HashMap());
while (idx < len) {
switch (formula.charAt(idx)) {
case '(':
// create a new inner map to hold atoms inside the parenthese
stack.push(new HashMap());
idx++;
break;
case ')':
idx++;
Map innerMap = stack.pop();
Map outerMap = stack.peek();
int cnt = nextNum();
// multiple the inner cnt with the )n's n, and join to the outerMap
for (String s : innerMap.keySet()) {
outerMap.put(s, outerMap.getOrDefault(s, 0) + innerMap.get(s) * cnt);
}
break;
default:
// atom
// record this atom's number
Map map = stack.peek();
String atom = nextAtom();
int n = nextNum();
map.put(atom, map.getOrDefault(atom, 0) + n);
}
}
// turn outest map to a treeMap so that the atom name is ordered
TreeMap treeMap = new TreeMap<>(stack.peek());
StringBuilder sb = new StringBuilder();
for (String s : treeMap.keySet()) {
sb.append(s);
int cnt = treeMap.get(s);
if (cnt > 1) {
sb.append(String.valueOf(cnt));
}
}
return sb.toString();
}
Meanwhile, we need to handle each atom’s name and next number. Java support useful functions to easily reach the goal:
private String nextAtom() {
int start = idx++;
// continue matching while next character is a lowercase character
while (idx < len && Character.isLowerCase(formula.charAt(idx))) {
idx++;
}
return formula.substring(start, idx);
}
private int nextNum() {
// If the following is not a number, return the default 1
if (idx == len || !Character.isDigit(formula.charAt(idx))) {
return 1;
}
int start = idx++;
// continue matching while next character is a digit
while (idx < len && Character.isDigit(formula.charAt(idx))) {
idx++;
}
return Integer.parseInt(formula.substring(start, idx));
}
Complete code:
class Solution{
String formula;
int idx, len;
public String countOfAtoms(String fml) {
this.formula = fml; // the chemical formula
this.idx = 0; // the index we are handling
this.len = formula.length();
// create the map stack
Deque> stack = new ArrayDeque<>();
// default map containing atoms outside any parentheses, eg:Fe
in Fe2(SO4)3
stack.push(new HashMap());
while (idx < len) {
switch (formula.charAt(idx)) {
case '(':
// create a new inner map to hold atoms inside the parenthese
stack.push(new HashMap());
idx++;
break;
case ')':
idx++;
Map innerMap = stack.pop();
Map outerMap = stack.peek();
int cnt = nextNum();
// multiple the inner cnt with the )n's n, and join to the outerMap
for (String s : innerMap.keySet()) {
outerMap.put(s, outerMap.getOrDefault(s, 0) + innerMap.get(s) * cnt);
}
break;
default:
// atom
// record this atom's number
Map map = stack.peek();
String atom = nextAtom();
int n = nextNum();
map.put(atom, map.getOrDefault(atom, 0) + n);
}
}
// turn outest map to a treeMap so that the atom name is ordered
TreeMap treeMap = new TreeMap<>(stack.peek());
StringBuilder sb = new StringBuilder();
for (String s : treeMap.keySet()) {
sb.append(s);
int cnt = treeMap.get(s);
if (cnt > 1) {
sb.append(String.valueOf(cnt));
}
}
return sb.toString();
}
private String nextAtom() {
int start = idx++;
// continue matching while next character is a lowercase character
while (idx < len && Character.isLowerCase(formula.charAt(idx))) {
idx++;
}
return formula.substring(start, idx);
}
private int nextNum() {
// If the following is not a number, return the default 1
if (idx == len || !Character.isDigit(formula.charAt(idx))) {
return 1;
}
int start = idx++;
// continue matching while next character is a digit
while (idx < len && Character.isDigit(formula.charAt(idx))) {
idx++;
}
return Integer.parseInt(formula.substring(start, idx));
}
}
Original: https://www.cnblogs.com/liuzhch1/p/16413887.html
Author: liuzhch1
Title: LeetCode 726: 原子的数量-栈和Map的结合以及字符串处理 | Number of Atoms-Combination of stack, map and string processing
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/606688/
转载文章受原作者版权保护。转载请注明原作者出处!