Krammer's blog

https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string/ from Google

Thinking process:

This is a state machine problem. If we meet a left bracket, the follow word is a key, so we change the state to know that the following word is a key. If we meet a right bracket, we know that we see a complete keyword and need to find the value, so we change back to the normal state. In the normal state, we just append the original characters.

Here is the code.

 1class Solution {
 2public:
 3    string evaluate(string s, vector<vector<string>>& knowledge) {
 4        unordered_map<string, string> mp;
 5        for (auto k : knowledge) {
 6            mp[k[0]] = k[1];
 7        }
 8        string ans = "";
 9        string key = "";
10        int state = 0;
11        for (auto c : s) {
12            if (c == '(') {
13                state = 1;
14            } else if (c == ')') {
15                state = 0;
16                if (mp.count(key)) {
17                    ans += mp[key];
18                } else {
19                    ans += '?';
20                }
21                key = "";
22            } else if (state == 1) {
23                key += c;
24            } else {
25                ans += c;
26            }
27        }
28        return ans;
29    }
30};

Editorial: LeetCode 1807 Evaluate the Bracket Pairs of a String