Number of Atoms - LeetCode solutions

Problem

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.

The test cases are generated so that all the values in the output fit in a 32-bit integer.

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}.

Constraints:

1 <= formula.length <= 1000
formula consists of English letters, digits, '(', and ')'.
formula is always valid.

Solution

/**
 * @param {string} formula
 * @return {string}
 */
var countOfAtoms = function(formula) {
  // we split the formula by "letters", "numbers", "(", ")"
  // so we don't have to check the formula letter by letter.
  formula = formula.match(/[A-Z][a-z]*|\d+|[()]/g);
  const stk = [];
  let temp = {};
  for (let i = 0; i < formula.length; i += 1) {
    if (formula[i] == '(') {
      // A nested level starts here, we record what we have for
      // the temporary results to the stack.
      stk.push(temp);
      // And start new.
      temp = {}; // 
    } else if (formula[i].match(/^\d+$/)) {
      // We see a number, and before the number is a ')',
      if (formula[i-1] == ')') {
        // We multiply the number with the temporary results.
        for (const k in temp) temp[k] *= +formula[i];
        // And we merge the top of the stack to the temporary
        // result so it's always updated.  
        mergeTemp(stk.pop(), temp);
      } else {
        // If it's a letter before the number, we need to 
        // subtract it by 1, because we had it initialized as
        // { X: 1 } to begin with.
        temp[formula[i-1]] += +formula[i] - 1;
      }
    } else if (formula[i] != ')') {
      // If it's just letters, we update its count.
      // Note we might have the same letter on the same level.
      // For example, "H2...H4"
      temp[formula[i]] = temp[formula[i]] + 1 || 1;
    }
  }

  // 1. Make sure we merge all the temporary results on the
  //    outermost level, if thy exist on the stack.
  // 2. This is the bug where a input like "Mg(H2O)N" this would
  //    not include { Mg: 1 } to the final result, because we only 
  //    try merging stack top to temp when we see a number after
  //    ')' on line 21, but in this case, we don't see a number, so
  //    we just move on and leave { Mg: 1 } on the stack.
  // 3. We could potentially remove these kind of parenthesis,
  //    however, I don't think it's worth the trouble.
  while (stk.length) mergeTemp(stk.pop(), temp);

  // Now we have all the key-value pairs, let's sort them
  // and print them in order with desired format.
  let ans = '';
  Object.keys(temp).sort((a, b) => a.localeCompare(b)).map(k => {
    ans += `${k}${temp[k] > 1 ? temp[k] : ''}`;
  });
  return ans;

  function mergeTemp(prev, temp) {
    for (const k in prev) {
      temp[k] = temp[k] + prev[k] || prev[k];
    }
  }
};

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).