Time:O(n) Space:O(n) C++ 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; } }; JAVA 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(); } }