Code Implementation

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        mapping = {k: v for k, v in knowledge}
        result = []
        i = 0
        n = len(s)
        while i < n:
            if s[i] == '(':
                j = i + 1
                while s[j] != ')':
                    j += 1
                key = s[i+1:j]
                result.append(mapping.get(key, '?'))
                i = j + 1
            else:
                result.append(s[i])
                i += 1
        return ''.join(result)
      

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string, string> mapping;
        for (auto& pair : knowledge) {
            mapping[pair[0]] = pair[1];
        }
        string result;
        for (int i = 0; i < s.size();) {
            if (s[i] == '(') {
                int j = i + 1;
                while (s[j] != ')') ++j;
                string key = s.substr(i + 1, j - i - 1);
                if (mapping.count(key))
                    result += mapping[key];
                else
                    result += '?';
                i = j + 1;
            } else {
                result += s[i++];
            }
        }
        return result;
    }
};
      

class Solution {
    public String evaluate(String s, List<List<String>> knowledge) {
        Map<String, String> map = new HashMap<>();
        for (List<String> pair : knowledge) {
            map.put(pair.get(0), pair.get(1));
        }
        StringBuilder result = new StringBuilder();
        int i = 0, n = s.length();
        while (i < n) {
            if (s.charAt(i) == '(') {
                int j = i + 1;
                while (s.charAt(j) != ')') j++;
                String key = s.substring(i + 1, j);
                result.append(map.getOrDefault(key, "?"));
                i = j + 1;
            } else {
                result.append(s.charAt(i++));
            }
        }
        return result.toString();
    }
}
      

var evaluate = function(s, knowledge) {
    const map = new Map();
    for (const [k, v] of knowledge) map.set(k, v);
    let result = '';
    for (let i = 0; i < s.length;) {
        if (s[i] === '(') {
            let j = i + 1;
            while (s[j] !== ')') j++;
            const key = s.slice(i + 1, j);
            result += map.has(key) ? map.get(key) : '?';
            i = j + 1;
        } else {
            result += s[i++];
        }
    }
    return result;
};
      

Problem Description

You are given a string s that may contain substrings enclosed in brackets (i.e., (key)), and a list called knowledge, where each element is a pair [key, value]. Your task is to evaluate the string by replacing every bracketed key with its corresponding value from knowledge. If a key does not exist in knowledge, replace it with a question mark '?'.

Constraints:

• Each bracketed substring has exactly one key.
• All keys and values consist of lowercase English letters.
• There will be no nested or overlapping brackets.
• The mapping in knowledge is unique for each key.

Thought Process

At first glance, the problem looks like a string replacement task. The simplest approach would be to scan the string and replace each bracketed key by searching for its value in knowledge. However, directly searching the knowledge list for each key would be inefficient, especially if the list is large.

To optimize, we can preprocess knowledge into a dictionary or hash map, allowing us to look up each key in constant time. Then, as we scan the string, whenever we encounter a bracket, we extract the key, look up its value in the map, and append the value (or '?' if missing) to the result.

This approach avoids unnecessary repeated searches and efficiently handles the replacements in a single pass through the string.

Solution Approach

• Step 1: Convert the knowledge list into a hash map or dictionary for fast lookup. This makes checking for a key's value O(1).
• Step 2: Initialize an empty result string (or string builder).
• Step 3: Iterate through the string s character by character.
  • If the current character is not a '(', simply add it to the result.
  • If the current character is '(', start reading characters until you find the closing ')'. The substring in between is the key.
  • Look up the key in the hash map. If found, append its value to the result. If not found, append '?'.
• Step 4: Continue until the end of the string, then return the result.

We use a hash map for fast lookups, and a single scan of the string ensures efficiency. No extra data structures are needed besides the map and the output string.

Example Walkthrough

Input: s = "hi(name), you are (status)!", knowledge = [["name","bob"], ["status","awesome"]]

1. Convert knowledge to a map: {"name": "bob", "status": "awesome"}.
2. Start scanning s:
   • Characters 'h', 'i' → append to result.
   • Encounter '(', start key: read until ')', get name.
   • Lookup 'name' in map → 'bob', append to result.
   • Continue: ',', ' ', 'y', 'o', 'u', ' ', 'a', 'r', 'e', ' ' → append.
   • Encounter '(', start key: read until ')', get status.
   • Lookup 'status' in map → 'awesome', append to result.
   • Exclamation mark → append.
3. Final result: "hibob, you are awesome!"

If a key was missing, e.g. (status2), it would be replaced by '?'.

Time and Space Complexity

• Brute-force approach: For every bracketed key, search the entire knowledge list. If there are K keys and N knowledge pairs, time is O(K*N).
• Optimized approach:
  • Building the hash map: O(N), where N is the number of knowledge pairs.
  • Scanning the string: O(S), where S is the length of the input string.
  • Lookup per key: O(1), thanks to the hash map.
  • Total time complexity: O(N + S).
  • Space complexity: O(N) for the hash map and O(S) for the result string.

Summary

By converting the knowledge list into a hash map, we enable fast lookups for each key found in the string. The algorithm efficiently scans the input string once, replacing bracketed keys with their corresponding values or a question mark if missing. This approach is both simple and efficient, leveraging basic data structures to solve the problem elegantly.