726. 原子的數量

思路

在字串當中，會有以下幾種情況：

• 大小寫字母：遇到大寫字母，也就表示統計到現在的元素名稱結束，需要結算。
• 數字：統計到遇見數字以外字元時，
• 左右括號：當遇到左括號時，需要結算，知道括號內的元素後，用右括號後的數字加倍。
  • 由於是先知道元素，才知道加倍的數字，在知曉數字之前，要紀錄「等待加倍的元素列表」

用變數name紀錄元素名稱，cnt紀錄數字，history紀錄「等待加倍的元素列表」。 map<string,int>紀錄元素對應的出現次數。 dfs(i)代表從位置i開始往後計算元素。

假設現在給定A3B4(CD)2(Fe2O3)4 一開始呼叫dfs(0)

• 最初遇到大寫A，結算，
  • name = ""，cnt = 0，map = []，history = []
• 遇到B，結算，
  • name = A，cnt = 3，map = [{A, 3}]，history = []
• 遇到(，需要開始計算括號內部的元素，先結算現有的，並呼叫dfs(5)
  • name = B，cnt = 4，map = [{A, 3}, {B, 4}]，history = []
  • 呼叫dfs(5)
    • 遇到C，D，最後map = [{C, 0}, {D, 0}]，回傳map
    • 為了讓上游的dfs(0)知道最後所在的位置，用where紀錄，where = 7。
• dfs(0)接收到dfs(5)傳回的map，紀錄到history
  • name = ""，cnt = 2，map = [{A,3}, {B, 4}]，history = [{C, 0}, {D, 0}]
• 遇到(，需要開始計算括號內部的元素，先結算現有的，並呼叫dfs(5)。
  • name = ""，cnt = 2 map = [{A, 3}, {B, 4}, {C, 2}, {D, 2}]，history = [{C, 0}, {D, 0}]

1. 在整個過程當中，name跟history不可能同時有資訊，因為在遇到(時，history會被算出來，name會被結算。
2. cnt在填入時，數字0實際上代表有出現一次。
3. 到終點時，最後的紀錄需要記得計入。

程式碼

遞迴

class Solution {
private:
    void fill(map<string, int>& mp, string name, map<string, int>& history, int cnt) {
        // 把元素加 cnt 倍
        if(!name.empty() || !history.empty()) {
            cnt = cnt == 0 ? 1 : cnt;
            // 看來自哪裡
            if(!name.empty()) {
                mp[name] += cnt;
            }
            else {
                for(auto& [k, v] : history) {
                    mp[k] += v * cnt;
                }
            }
        }
    }
public:
    string countOfAtoms(string s) {
        int n = s.length();
        int where = 0;
        
        auto dfs = [&](this auto&&dfs, int i) -> map<string, int> {
            map<string, int> mp, history;
            string name;
            int cnt = 0;
            while(i < n && s[i] != ')') {
                if(islower(s[i])) {
                    name += s[i++];
                }
                else if(isdigit(s[i])) {
                    cnt = cnt * 10 + (s[i++] - '0');
                }
                else { // 大寫字母或是左括號, 需要結算
                    fill(mp, name, history, cnt);
                    cnt = 0; name = ""; history.clear(); // 結算後清空
                    if(isupper(s[i])) { // 大寫字母
                        name = s[i++];
                    }
                    else { // 左括號
                        history = dfs(i + 1);
                        i = where + 1;
                    }
                }
            }
            // s[i] == ')' 
            fill(mp, name, history, cnt); // 填入最後的資訊
            where = i;
            return mp;
        };
        
        map<string, int> mp = dfs(0);
        string res;
        for(auto& [name, cnt] : mp) {
            res += name;
            if(cnt > 1) res += to_string(cnt);
        } 
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n^2)$
• 空間複雜度：$O(n)$