LeetCode-726 原子的數量 遞歸

題目鏈接：LeetCode-726 原子的數量

給你一個字符串化學式 formula ，返回 每種原子的數量 。

原子總是以一個大寫字母開始，接著跟隨 0 個或任意個小寫字母，表示原子的名字。

如果數量大于 1，原子后會跟著數字表示原子的數量。如果數量等于 1 則不會跟數字。

例如，“H2O” 和 “H2O2” 是可行的，但 “H1O2” 這個表達是不可行的。
兩個化學式連在一起可以構成新的化學式。

例如 “H2O2He3Mg4” 也是化學式。
由括號括起的化學式并佐以數字（可選擇性添加）也是化學式。

例如 “(H2O2)” 和 “(H2O2)3” 是化學式。
返回所有原子的數量，格式為：第一個（按字典序）原子的名字，跟著它的數量（如果數量大于 1），然后是第二個原子的名字（按字典序），跟著它的數量（如果數量大于 1），以此類推。

示例 1：
輸入：formula = “H2O”
輸出：“H2O”
解釋：原子的數量是 {‘H’: 2, ‘O’: 1}。

示例 2：
輸入：formula = “Mg(OH)2”
輸出：“H2MgO2”
解釋：原子的數量是 {‘H’: 2, ‘Mg’: 1, ‘O’: 2}。

示例 3：
輸入：formula = “K4(ON(SO3)2)2”
輸出：“K4N2O14S4”
解釋：原子的數量是 {‘K’: 4, ‘N’: 2, ‘O’: 14, ‘S’: 4}。

示例 4：
輸入：formula = “Be32”
輸出：“Be32”

提示：

• 1 <= formula.length <= 1000
• formula 由英文字母、數字、’(’ 和 ‘)’ 組成
• formula 總是有效的化學式
• 輸出的所有值總是在 32-bit 整數范圍內

本題并沒有特別復雜、特別難理解的思路，但是對于各種情況需要妥善地加以處理，再配合遞歸的思想和 map 即可解出。

首先我們來分析以下，我們在遍歷給定的字符串的時候會遇到以下幾種情況：

1. 常規情況

   這里的情況指的是常規的字符和數字，即沒有括號的情況。在這種情況下，我們知道，大寫字母及其后跟著的小寫字母表示的是化學元素的名稱；而元素名稱后面又有兩種情況，一是后面直接跟其他大寫字母，這種情況下即元素個數缺省，默認為1，另一種情況是后面跟著數字，則數字表示該元素的原子個數。

2. 括號

   括號及嵌套括號的出現是這個題要仔細處理的一個情況。對于這種多層括號嵌套，最里面的括號中就是我們上面的常規情況，而不同級的括號嵌套這種情況非常適合我們用遞歸的方式進行處理。

在具體實現中，我們將遍歷字符串中遇到的字符分為以下三種情況：

1. 遇到 (

   當遇到左括號時，我們要開始準備遞歸，在這種情況下，對當前括號里的子串進行遞歸調用，并用一個子 map 來接收當前括號內子串的原子名稱及個數。當我們遇到有括號會退出遞歸函數，注意當退出遞歸函數時我們需要記錄其后面的一個數字，并將它乘到我們的子串得到的子 map 所統計的原子個數上。

2. 遇到 )

   遇到右括號時，我們肯定在之前遇到過一個左括號并進入遞歸函數，這時我們只需返回，并讓遍歷索引往后走一步即可。

3. 其他情況

   其他情況即上述常規情況，我們遇到的是代表原子名稱的字母和代表原子個數的數字。我們會分別實現兩個函數來獲取原子名稱和個數。

其他需要注意的點：

• 題目中要求的字典序，map 會自動幫我們排序。
• 整個過程中維護的遍歷索引 i 需要再函數間傳遞時使用引用傳遞。

完整代碼：

class Solution {
private:int get_num(string& s, int& i) {string num = "";while (isdigit(s[i])) {num += s[i++];}return num.empty() ? 1 : stoi(num);}string get_name(string& s, int& i) {string name = "";while (isalpha(s[i]) && (name.empty() || islower(s[i]))) {name += s[i++];}return name;}map<string, int> get_map(string& s, int& i) {map<string, int> ans;while (i != s.length()) {if (s[i] == '(') {map<string, int> temp = get_map(s, ++i);int cnt = get_num(s, i);for (auto& kv : temp) {ans[kv.first] += kv.second * cnt;}}else if (s[i] == ')') {++i;return ans;}else {string name = get_name(s, i);int cnt = get_num(s, i);ans[name] += cnt;}}return ans;}public:string countOfAtoms(string formula) {int i = 0;string ans;for (auto& kv : get_map(formula, i)) {ans += kv.first;if (kv.second > 1) {ans += to_string(kv.second);}}return ans;}
};

Ref：

https://leetcode-cn.com/problems/number-of-atoms/

https://riba2534.blog.csdn.net/article/details/88591566