Title Description:
Give you a string s, which contains pairs of parentheses, each containing a non empty key.
For example, in the string "(name) is (age) yearsolve", there are two pairs of parentheses, which contain the keys "name" and "age" respectively.
You know the values corresponding to many keys. These relationships are represented by a two-dimensional string array knowledge, where knowledge[i] = [keyi, valuei], indicating that the value corresponding to key keyi is valuei.
You need to replace all parenthesis pairs. When you replace a bracket pair and its key is keyi, you need to:
Replace keyi and parentheses with the corresponding value valuei.
If you can't know the value of a key from knowledge, you need to use keyi and parentheses with a question mark "?" Replace (quotation marks are not required).
Each key in knowledge can only appear once at most. There will be no nested parentheses in s.
Please return the result string after replacing all bracket pairs.

Example 1:
Input: s = "(name) is (age) yearsolve", knowledge = [["name", "bob"], ["age", "two"]]
Output: "bobistwoyearsolid"
Explanation:
The value corresponding to the key "name" is "bob", so replace "(name)" with "bob".
The value corresponding to the key "age" is "two", so replace "(age)" with "two".

Example 2:
Input: s = "hi(name)", knowledge = [["a", "b"]]
Output: "hi?"
Explanation: because you don't know the value corresponding to the key "name", use " Replace "(name)".

Example 3:
Input: s = "(a)(a)(a)aaa", knowledge = [["a", "yes"]]
Output: "yesaaa"
Explanation: the same key may appear multiple times in s.
The value corresponding to key "a" is "yes", so replace all "(a)" with "yes".
Note that "a" not in parentheses does not need to be replaced.

Example 4:
Input: s = "(a)(b)", knowledge = [["a", "B"], ["B", "a"]]
Output: "ba"

Tips:
1 <= s.length <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1 <= keyi.length, valuei.length <= 10
s contains only lowercase letters and parentheses' ('and').
Every left parenthesis' ('in s has a corresponding right parenthesis')'.
Every pair of keys in parentheses in s will not be empty.
There will be no nested parenthesis pairs in s.
keyi and valuei contain only lowercase letters.
keyi in knowledge will not be repeated.

Method 1:
Main ideas: Problem solving link summary
(1) Simulation process;
(2) First, use the key value pairs given by hash statistics;
(3) Find out each key in the original string and replace it with the corresponding string;

class Solution {
public:
    string evaluate(string s, vector<vector<string>>& knowledge) {
		unordered_map<string, string> mp;
		for (auto&it : knowledge) {//Use hash to count keys and values
			mp[it[0]] = it[1];
		}
		string res;//Store results
		int index = 0;//Indexes
		while (index < s.size()) {
			if (s[index] == '(') {//Find the key that needs to be replaced
				++index;
				int cur_begin = index;//Start position of current key
				while (index < s.size() && s[index] != ')') {//The end position of the current key is obtained at the end of the cycle
					++index;
				}
				string cur_str = s.substr(cur_begin, index - cur_begin);//Get current key
				if (mp.count(cur_str)) {//Judge whether the current key is stored and replace it with the corresponding value
					res += mp[cur_str] ;
				}
				else {
					res += "?";
				}
			}
			else {
				res += s[index];//Get the normal string part
			}
			++index;
		}
		return res;
	}
};

//go language implementation

func evaluate(s string, knowledge [][]string) string {
    mp := map[string]string{}
    for i:=0;i<len(knowledge);i++ {
        mp[knowledge[i][0]]=knowledge[i][1]
    }
    res := ""
    index := 0
    for index<len(s) {
        if s[index]=='(' {
            index++
            cur_begin := index
            for index<len(s)&&s[index]!=')' {
                index++
            }
            if _,exist := mp[s[cur_begin:index]];exist {
                res+=mp[s[cur_begin:index]]
            }else{
                res+="?"
            }
        }else{
            res+=string(s[index])
        }
        index++
    }
    return res
}