Leetcode 726. Number of atoms

This is my second article about getting started

The title

Given a chemical formula (as a string), return the number of each atom.

An atom always starts with a capital letter, followed by zero or any lowercase letter to indicate the atom’s name.

If the number is greater than 1, the number of atoms is followed by a number. If the quantity is equal to 1, the number will not be followed. For example, H2O and H2O2 are ok, but H1O2 is not.

Two chemical formulas are joined together to form a new chemical formula. For example, H2O2He3Mg4 is also a chemical formula.

A chemical formula and a number (optionally added) in parentheses are also chemical formulas. For example, (H2O2) and (H2O2)3 are chemical formulas.

Given a chemical formula formula, return the number of all atoms. The format is: the name of the first (in lexicographical order) atom, followed by its number (if the number is greater than 1), then the name of the second atom (in lexicographical order), followed by its number (if the number is greater than 1), and so on.

Example 1: Input: formula = "H2O" Output: "H2O" Explanation: The number of atoms is {'H': 2, 'O': 1}. Example 2: Input: formula = "Mg(OH)2" Output: "H2MgO2" Explanation: The number of atoms is {'H': 2, 'Mg': 1, 'O': 2}. Example 3: Input: formula = "K4(ON(SO3)2)2" Output: "K4N2O14S4" Explanation: The number of atoms is {'K': 4, 'N': 2, 'O': 14, 'S': 4}. Example 4: Input: formula = "Be32" Output: "Be32"Copy the code

Their thinking

Use recursion to implement the function of stack

1. When ‘(‘ is encountered, the elements in parentheses are recursed
2. When ‘)’ is encountered, take the map out of the stack (the number of atoms in the map needs to be multiplied by the number after the parentheses, if not, the default is 1), go back to the upper function, and merge the returned map
3. In recursive functions, when a letter is encountered, that is, atoms need to be processed, the number of atoms is counted, and the number of occurrences of the atom is recorded using Treemap

code

class Solution {
    int next=-1;
    public String countOfAtoms(String formula) {

        StringBuilder builder = new StringBuilder();
        Map<String, Integer> map = count(formula, 0);
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            builder.append(entry.getKey()).append(entry.getValue()==1?"":entry.getValue());

        }
        return builder.toString();

    }
    public Map<String,Integer> merge(Map<String,Integer> a,Map<String,Integer> b) {
        for (Map.Entry<String,Integer> c:b.entrySet())
        {
            a.put(c.getKey(),a.getOrDefault(c.getKey(),0)+c.getValue());
        }
        return a;
    }
    public Map<String,Integer> count(final String formula, int l) {
        Map<String, Integer> map = new TreeMap<String, Integer>();
        for (inti=l; i<formula.length();) {if(formula.charAt(i)=='(')
            {
                Map<String, Integer> count = count(formula, i + 1);
                merge(map,count);
                i=next;
            }else if(formula.charAt(i)==') ') {The default value is 1
                if(i+1>=formula.length()||! Character.isDigit(formula.charAt(i+1)))// No digits
                    next=i+1;
                else {// Extract the number
                    i++;
                    int s=i;
                    while (i<formula.length()&&Character.isDigit(formula.charAt(i)))
                        i++;
                    int cur=Integer.parseInt(formula.substring(s,i));
                    map.replaceAll((k,v)->v*cur);
                    next=i;
                }
                return map;

            } else if(Character.isUpperCase(formula.charAt(i))) {
// If uppercase is encountered, lowercase is also ascribed to this atom
                int s = i;
                i++;
                while (i < formula.length() && Character.isLowerCase(formula.charAt(i)))
                    i++;
                String key = formula.substring(s, i);
                int cur;
                if(i >= formula.length() || ! Character.isDigit(formula.charAt(i))) cur =1;
                else {
                    s = i;
                    while (i < formula.length() && Character.isDigit(formula.charAt(i)))
                        i++;
                    cur = Integer.parseInt(formula.substring(s, i));
                }
                map.put(key, map.getOrDefault(key, 0) + cur); }}returnmap; }}Copy the code