Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

First, understand the topic

Attached is a link to the original problem: 394. String decoding

Given an encoded string, return its decoded string.

The encoding rule is k[encoded_string], indicating that the encoded_string inside the square brackets is repeated exactly K times. Note that k is guaranteed to be a positive integer.

You can assume that the input string is always valid; There are no extra Spaces in the input string, and the input square brackets are always formatted.

In addition, you can assume that the raw data does not contain numbers, and that all numbers represent only the number of repetitions k, such as no input like 3a or 2[4].

Ii. Solution analysis

This problem is solved using stacks in data structures. So let’s look at the steps to solve the problem, as follows:

  • Define two stacks, one for multiples and one for strings to be concatenated.
  • That defines a numbernumVariable to store and concatenate multiples.
  • Defines a stringresultVariable used to concatenate strings.
  • Character by character scanning will be encountered4Kind of situations:1.Encounter numbers;2.encounter[ ；3.encounter] ；(4)Encounter letters.

Three, code implementation

Based on the above solution, we will use JS to implement this problem. The specific implementation code is as follows:

/ * * *@param {string} s
 * @return {string}* /
​
 let decodeString = function(s) {
    // 1. Store multiple stacks
    let numStack = [];
    // 2. Stack to store STR to be spliced
    let strStack = [];
    // 3.
    let num = 0;
    // 4. String "porter"
    let result = ' ';
    // 5. Character-by-character scanning
    for (let char of s) {
        // 5.1 Encountering a number
        if (!isNaN(char)) {
            // 5.1.1 Calculate the multiples
            num = num * 10 + Number(char); 
        } 
        // 5.2 Encountering [
        else if (char === '[') {
            // 5.2.1 Place the concatenated result in the strStack
            strStack.push(result);
            // 5.2.2 Clear zero after loading
            result = ' ';
            // 5.2.3 Multiple num enters the stack wait
            numStack.push(num);
            // 5.2.4 Clear after loading
            num = 0;
            
        } 
        // when [is encountered], two stacks are pushed out of the stack
        else if (char === '] ') {
            5.3.1 Obtaining the Number of Copy Times
            let repeatTimes = numStack.pop();
            // 5.3.2 Building a substring
            result = strStack.pop() + result.repeat(repeatTimes); 
        } 
        If a letter is encountered, append to the result string
        else{ result += char; }}// 6. Final return result
    return result;
};
​
console.log(decodeString('3[a2[c]]')); // accaccacc
console.log(decodeString('3[a]')); // aaa
Copy the code

The above is about string encoding problem solution, I do not know whether it is helpful to small friends?

We’ll see you next time at 👋👋👋