LeetCode：394. String decoding

Given an encoded string , Returns the decoded string .

The coding rule is : k[encoded_string], Represents the encoded_string Just repeat k Time . Be careful k Positive integer guaranteed .

You can think that the input string is always valid ; There are no extra spaces in the input string , And the square brackets entered always meet the format requirements .

Besides , You can assume that the raw data does not contain numbers , All numbers only indicate the number of repetitions k , For example, there is no such thing as 3a or 2[4] The input of .

Example 1：

 Input ：s = "3[a]2[bc]"
 Output ："aaabcbc"

Example 2：

 Input ：s = "3[a2[c]]"
 Output ："accaccacc"

Example 3：

 Input ：s = "2[abc]3[cd]ef"
 Output ："abcabccdcdcdef"

Example 4：

 Input ：s = "abc3[cd]xyz"
 Output ："abccdcdcdxyz"

Tips ：

• 1 <= s.length <= 30
• s By lowercase letters 、 Numbers and square brackets ‘[]’ form
• s Guarantee is a It works The input of .
• s The value range of all integers in is [1, 300]

---

Their thinking

1. From inside to outside , Solve layer by layer [ ], Need to keep memory of characters , So use the stack
2. Time to enter the stack ： encounter [ It means solving internal problems first , External numbers and letters go to the stack and wait

• When you meet [, The number that has been scanned is “ Multiple ”, Stack temporarily
• When you meet [, The scanned letters are also stacked and waiting , Wait until the decoding in brackets is finished , Can participate in the construction of strings together
  3. Time to get out of the stack ： encounter ] It means that the scanning of the inner layer is finished , Top element of stack （ I met you recently “ Multiple ” And letters ） You can get out of the stack , Jointly participate in the construction of substrings

Code

/** * @param {string} s * @return {string} */
var decodeString = function(s) {
    
    let numStack = [];        //  Stack of multiples 
    let strStack = [];        //  save   To be spliced str  The stack 
    let num = 0;              //  Temporary multiple 
    let result = '';          //  Temporary string 
    for (const char of s) {
       //  Character by character scanning 
        if (!isNaN(char)) {
       //  When it comes to numbers 
            num = num * 10 + Number(char); //  Calculate multiple 
        } else if (char == '[') {
      //  encounter  [
            strStack.push(result); // result String into stack 
            result = '';           
            numStack.push(num);    //  Multiple num Enter the stack and wait 
            num = 0;               
        } else if (char == ']') {
      //  encounter  ], The stack of two stacks comes out of the stack 
            let repeatTimes = numStack.pop(); //  Number of copies obtained 
            result = strStack.pop() + result.repeat(repeatTimes); //  Build substrings 
        } else {
                       
            result += char;        //  Letters encountered , Append to result strand 
        }
    }
    return result;
};