evaluate-the-bracket-pairs-of-a-string.cpp

// Time:  O(n + m)
// Space: O(n + m)

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> lookup;
        for (const auto& pair : knowledge) {
            lookup[pair[0]] = pair[1];
        }
        string result, curr;
        bool has_pair = false;;
        for (int i = 0; i < size(s); ++i) {
            if (s[i] == '(') {
                has_pair = true;
            } else if (s[i] == ')') {
                has_pair = false;
                if (lookup.count(curr)) {
                    for (const auto& c : lookup[curr]) {
                        result.push_back(c);
                    }
                } else {
                    result.push_back('?');
                }
                curr.clear();
            } else if (has_pair) {
                curr.push_back(s[i]);
            } else {
                result.push_back(s[i]);
            }
        }
        return result;
    }
};