3484. 設計電子表格

思路

用一個哈希表，把整個字串作為鍵，不需要分離行列。

• setCell：把數值插入到哈希表裡面。
• setCell：把給訂的鍵對應的數值重新設定為零
• getValue：忽略第一個字元=，根據+分離前後兩個鍵，並看各自第一位是否為數字。
  • 如果是數字，那麼整個鍵都是數字。
  • 如果是英文符號，就是哈希表對應的數值。

程式碼

class Spreadsheet {
private:
    unordered_map<string, int> cellValue;
public:
    Spreadsheet(int rows) {}
    
    void setCell(string cell, int value) {
        cellValue[cell] = value;
    }
    
    void resetCell(string cell) {
        cellValue[cell] = 0;
    }
    
    int getValue(string formula) {
        int len = formula.length();
        int i = formula.find('+');
        string sa = formula.substr(1, i - 1);
        string sb = formula.substr(i + 1);
        int a = isdigit(sa[0]) ? stoi(sa) : cellValue[sa];
        int b = isdigit(sb[0]) ? stoi(sb) : cellValue[sb];
        return a + b;
    }
};

複雜度分析

• 時間複雜度：初始化$O(1)$，其他是$O(L)$，$L$ 是cell或是formula的長度。
• 空間複雜度：$O(qL)$，q是setCell的調用次數。