LeetCode 726: Number of Atoms ·

基本資料
#

難易度: hard 第一次嘗試：2026-07-11

提交紀錄：Wrong Answer ×3 → Accepted

解題思路
#

化學式有三種東西：

元素：一個大寫字母，後面接 0 個以上的小寫字母，例如 H、Mg。
數字：可能有好幾位，沒寫就是 1。
括號：( ... ) 後面可以接一個倍數，沒寫就是 1。

用 index 從左到右解析，每次讀一個完整的 token：

讀到 (：在 stack 放一個標記。
讀到 )：讀出後面的倍數，把 stack 裡到 ( 為止的元素計數都乘上倍數，再放回去。
讀到大寫字母：讀完整個元素名稱和後面的數字，推進 stack。

最後把 stack 裡的計數加總，依元素名稱排序輸出。

我的嘗試
#

前三版都是「一個字元一個字元處理」，邊讀邊猜目前的字元屬於哪個 token，錯在好幾個邊界：

digits = "23456789"：漏了 0 和 1。題目說數量 1 不會寫出來，但 10、21 這種多位數還是會出現 0 和 1。
數字只讀一位：H12 會被讀成 H1 和 2。
) 後面沒有數字：例如 (OH)，括號裡的元素沒有被合併，) 標記一直留在 stack 裡。

第四版改成用 index 一次讀完一個完整的 token，每種 token 各自處理，就 AC 了。

正確解法
#

from collections import defaultdict

class Solution:
    def countOfAtoms(self, formula: str) -> str:
        n = len(formula)
        i = 0

        def read_number() -> int:
            nonlocal i
            start = i
            while i < n and formula[i].isdigit():
                i += 1
            return int(formula[start:i]) if i > start else 1

        stack = [defaultdict(int)]
        while i < n:
            ch = formula[i]
            if ch == "(":
                stack.append(defaultdict(int))
                i += 1
            elif ch == ")":
                i += 1
                mult = read_number()
                inner = stack.pop()
                for atom, cnt in inner.items():
                    stack[-1][atom] += cnt * mult
            else:
                start = i
                i += 1
                while i < n and formula[i].islower():
                    i += 1
                atom = formula[start:i]
                stack[-1][atom] += read_number()

        counts = stack[0]
        return "".join(a + (str(counts[a]) if counts[a] > 1 else "") for a in sorted(counts))