LeetCode 1807. Replace parentheses in strings (C++)

The question says that there are no nested brackets, you only need to traverse the string, use an array to store the string that needs to be replaced; use a hash table to store the string corresponding to the string we need to replace; and then traverse the string Replace the string in brackets with the specified string or "?";
Original title link: https://leetcode.cn/problems/evaluate-the-bracket-pairs-of-a-string/description/

1. The topic is as follows:

You are given a string s that contains pairs of parentheses, each containing a non-null key.

For example, in the string "(name)is(age)yearsold", there are two parenthesis pairs containing the keys "name" and "age" respectively.
You know the values ​​corresponding to many keys, and these relationships are represented by the two-dimensional string array knowledge, where knowledge[i] = [keyi, valuei] , which means that the value corresponding to the key keyi is valuei .

You need to replace all parenthesis pairs. When you replace a pair of parentheses, and the key it contains is keyi, you need to:

Replace keyi and parentheses with the corresponding value valuei.
If you can't know the value corresponding to a key from knowledge, you need to replace keyi and parentheses with question marks "?" (no quotation marks required).
Each key will appear at most once in knowledge. There will be no nested parentheses in s.

Please return the result string after replacing all parenthesis pairs.

Example 1:

enter: s = "(name)is(age)yearsold", knowledge = [["name","bob"],["age","two"]]

The value for the key "name" is "bob", so replace "(name)" with "bob".
The value for the key "age" is "two", so replace "(age)" with "two".

Example 2:

enter: s = "hi(name)", knowledge = [["a","b"]]

Explanation: Since the value corresponding to the key "name" is not known, replace "(name)" with "?".

Example 3:

enter: s = "(a)(a)(a)aaa", knowledge = [["a","yes"]]

The same key may appear multiple times in s.
The value corresponding to the key "a" is "yes", so replace all occurrences of "(a)" with "yes".
Note that the "a" not in parentheses does not need to be replaced.


1 <= s.length <= 105
0 <= knowledge.length <= 105
knowledge[i].length == 2
1<= keyi.length, valuei.length <= 10
s contains only lowercase English letters and parentheses '(' and ')' .
Each opening parenthesis '(' in s has a corresponding closing parenthesis ')'.
The keys within each pair of parentheses in s will not be null.
There will be no nested parenthesis pairs in s.
keyi and valuei contain only lowercase English letters.
The keyi in knowledge will not be repeated.

2. The code is as follows:

class Solution {
//Idea 1: Traversing auxiliary arrays and hash tables
    Use a hash table to record the corresponding replacement relationship
    Use an auxiliary array to record the words that need to be replaced
    string evaluate(string s, vector<vector<string>>& knowledge) {
        unordered_map<string,string> mapTemp;
        vector<string> temp;
        for(int i=0;i<knowledge.size();i++){
        //Record strings enclosed in parentheses
        for(int i=0;i<s.length()-1;i++){
                string temp1;
        int pos=0;
        string res;
        int mark=0;
        for(int i=0;i<s.length();i++){
            //It will only take effect when mark is equal to 0, that is to say, the characters in brackets will not be added to res
            if((s[i]!='(' && s[i]!=')') && mark==0){
        return res;

Tags: Algorithm C++ leetcode Hash table

Posted by slipmatt2002 on Sat, 28 Jan 2023 07:41:06 +0530