class Solution {
 public:
  string evaluate(string s, vector<vector<string>>& knowledge) {
    string ans;
    unordered_map<string, string> map;

    for (const auto& list : knowledge)
      map["(" + list[0] + ")"] = list[1];

    for (int i = 0; i < s.length(); ++i) {
      const char c = s[i];
      if (c == '(') {
        const int j = s.find_first_of(')', i);
        const string& key = s.substr(i, j - i + 1);
        ans += map.count(key) ? map[key] : "?";
        i = j;
      } else {
        ans += c;
      }
    }

    return ans;
  }
};

class Solution {
  public String evaluate(String s, List<List<String>> knowledge) {
    StringBuilder sb = new StringBuilder();
    Map<String, String> map = new HashMap<>();

    for (List<String> list : knowledge)
      map.put("(" + list.get(0) + ")", list.get(1));

    for (int i = 0; i < s.length(); ++i) {
      final char c = s.charAt(i);
      if (c == '(') {
        final int j = s.indexOf(')', i);
        sb.append(map.getOrDefault(s.substring(i, j + 1), "?"));
        i = j;
      } else {
        sb.append(c);
      }
    }

    return sb.toString();
  }
}