726. Number of Atoms ## 思路 先觀察: Aa(Bb)3 = AaBb3 Aa(Bb2)3 = AaBb6 (AaBb2)3 = Aa3Bb6 (Aa(Bb2)3)2 = Aa2Bb12 ((AaBb2)3)2 = Aa6Bb12 Cc(Aa(Bb2)3)2 = Aa2Bb12Cc 反向iterate, Stack存目前的num, Counter存atom的數量 - `)`: 把新的num * stack[-1] 加到stack - `(`: pop掉 - 大寫: 更新counter - 數字/小寫 最後再把counter sort產生output ## Complexity Time, Space: O(N) ## Code ```python class Solution: def countOfAtoms(self, formula: str) -> str: stack = [1] counter = Counter() atom, num = '', '' for ch in formula[::-1]: if ch.isdigit(): num = ch + num elif ch == ')': stack.append(stack[-1] * (int(num) if num else 1)) num = '' elif ch == '(': stack.pop() num = '' elif ch.islower(): atom = ch else: atom = ch + atom counter[atom] += stack[-1] * (int(num) if num else 1) atom, num = '', '' res = [] for atom in sorted(counter): if counter[atom] == 1: res.append(atom) else: res.append(f'{atom}{counter[atom]}') return ''.join(res) ``` -- ※ 發信站: 批踢踢實業坊(ptt-website.tw), 來自: 218.35.11.142 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1720918060.A.5B5