Bracket nesting problem (recommended Collection)

Catalog

One . String decoding

Two . Compression algorithm

3、 ... and . Score in parentheses

---

This article mainly brings you the solution of this bracket nesting problem , For this kind of bracket nesting problem, many old irons may be very headache . Here is a general solution to this kind of problem

  Let's take a look at the first question, string decoding ：

One . String decoding

1. Corresponding letecode link ：

394. String decoding - Power button （LeetCode）

2. Title Description ：

3. Their thinking ：

Traversal string ：

• If the current character is a number , namely '0' <= s[i] <= '9' Add this number to the number of times the substring is to be repeated num Because there may be more than one number , So pay attention to the original num Multiply by 10 Add the new figures .

• If the current character is an open parenthesis , namely s[i] == '[' Recursion , Notice every recursion num The return value of recursion is the index that has been traversed currently i And substrings ans After getting the return value, you will ans multiply num Add to res in , And reset num.

• If the current character is a closing bracket , namely s[i] == ']' Returns the current index i And the substring generated during the loop of the current recursive layer res

• If the currently traversed letter is directly added to the answer

Let's say "3[a]2[bc]" For example ：

  First meet 3 Is a number put it in num Just in the middle ：

Now come to the left parenthesis to make recursive calls, starting with the next question of the left parenthesis

At this point, the new recursive calling function comes a Location Add it to ans among

  Then continue to traverse down to the right bracket. At this time, the end of this recursion tells the place where it is called. The result of this recursion and the traversal to that position

After receiving the recursive result, use num Accumulate the results and add num Set as 0 Calculate from the next position returned by recursion . The following will not be repeated. In fact, they are all the same logic .

4. The corresponding code ：

class Solution {
  public:
    struct Info {
        Info(string a, int s) {
            ans = a;
            stop = s;
        }
        string ans;
        int stop;
    };
    string decodeString(string s) {
        return process(s, 0)->ans;
    }
    Info* process(const string& str, int index) {
        string ans;// Record answer 
        int num = 0; // Record the number of occurrences 
        while (str[index] != ']' && index < str.size()) {
            if (isalpha(str[index])) {// Letter 
                ans += str[index++];
                // Just put the letters directly into the answer 
            } else if (isdigit(str[index])) {
                // Numbers 
                num = num * 10 + str[index] - '0';
                index++;
            } else { // Yes '['
                Info* ret = process(str, index + 1);
                ans += addString(num, ret->ans);
                num = 0;
                index = ret->stop + 1;// Calculate from the next position returned recursively 
            }
        }
        return new Info(ans, index);

    }
    string addString(int num, string str) {
        string ans;
        for (int i = 0; i < num; i++) {
            ans += str;
        }
        return ans;
    }
};

Now let's look at a written test question of Tencent, which is very similar to the previous question

Two . Compression algorithm

1. Corresponding OJ link ：

Compression algorithm _ tencent 2020 Campus Recruitment - backstage _ Cattle from (nowcoder.com)

2. Title Description ：

3. Their thinking

This question is very similar to the previous question. Please see the code for details ：

• If the current character is a number , namely '0' <= s[i] <= '9' Add this number to the number of times the substring is to be repeated num Because there may be more than one number , So pay attention to the original num Multiply by 10 Add the new figures .
• If the current character is an open parenthesis , namely s[i] == '[' Recursion , The return value of recursion is the currently traversed index i And substrings ans Get the return value and add it to the current answer

4. The corresponding code ：

class Solution {
public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     * 
     * @param str string character string  
     * @return string character string 
     */
    struct Info
    {
      Info(const string&str,int end)
      {
          ans=str;
          stop=end;
      }
       string ans;
        int stop;
    };
    string compress(string str) {
        // write code here
       return process(str,0)->ans;
    }
    Info*process(const string&str,int index)
    {
        string ans;// Record answer 
        int num=0;
        while(index<str.size()&&str[index]!=']')
        {
            if(isalpha(str[index]))
            {
                ans+=str[index++];
            }
            else if(isdigit(str[index]))
            {
                num=num*10+str[index]-'0';
                index++;
            }
            else if(str[index]=='|')
            {
                index++;
            }
            else // Left parenthesis encountered 
            {
                Info*res=process(str,index+1);
                ans+=res->ans;
                index=res->stop+1;
          
            }
        }
        if(num!=0)
        {
           ans= addString(ans,num);
        }
        return new Info(ans,index);
    }
    string addString(string &str,int num)
    {
        string ans;
        for(int i=0;i<num;i++)
        {
            ans+=str;
        }
        return ans;
    }
};

3、 ... and . Score in parentheses

1. Corresponding letecode link ：

856. The fraction in brackets - Power button （LeetCode）

2. Title Description ：

 3. Their thinking ：

• When encountering the left parenthesis, call the recursive function directly
• ans+=max( Result returned by recursive function *2,1)
• Return the answer and calculate to that position

4. The corresponding code

class Solution {
  public:
    struct Info {
        Info(int _score, int _stop)
            : score(_score)
            , stop(_stop)
        {}
        int score;// score 
        int stop;// Calculate to that position 
    };
    int scoreOfParentheses(string s) {
        return process(s, 0)->score;
    }
    Info* process(const string& str, int index) {
        if (str[index] == ')') {// The right parenthesis returns directly 
            return new Info(0, index);
        }
        int ans = 0;
        // Record scores 
        while (index < str.size() && str[index] != ')') {
            Info* res = process(str, index + 1);
            ans += max(2 * res->score, 1);// Compare 
            index = res->stop + 1;// Start with the next question 
            delete res;
        }
        return new Info(ans, index);

    }
};