5714. 替换字符串中的括号内容

算法

哈希表

• 先将 knowledge 转化为哈希表数据结构
• 和第一题一样，使用 flag 表示当前是否正在括号内部，flag = true 时累积当前的括号内字符
• 每次遇到括号尾部的时候，查找哈希表进行对应的替换操作

C++ 代码

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> m;
        for (auto& p : knowledge) {
            m[p[0]] = p[1];
        }
        string t, cur;
        bool flag = false;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(')
                flag = true;
            else if (s[i] == ')') {
                if (m.count(cur))
                    t += m[cur];
                else
                    t += '?';
                cur = "";
                flag = false;
            } else {
                if (flag)
                    cur += s[i];
                else
                    t += s[i];
            }
        }
        return t;
    }
};

时间复杂度

• 构造哈希表：O(knowledge.length)
• 线性扫描：O(knowledge.length)
• 总时间复杂度：O(10^5)