Stack Title: String decoding

subject

Title and provenance

title ： String decoding

Source ：394. String decoding

difficulty

6 level

Title Description

requirement

Given an encoded string , Returns the decoded string .

The coding rule is ：$\text{k[encoded\_string]}$, Represents the $\text{encoded\_string}$ Just repeat $\text{k}$ Time . Be careful $\text{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 $\text{k}$, For example, there is no such thing as $\text{3a}$ or $\text{2[4]}$ The input of .

Example

Example 1：

Input ：$\text{s = "3[a]2[bc]"}$
Output ：$\text{"aaabcbc"}$

Example 2：

Input ：$\text{s = "3[a2[c]]"}$
Output ：$\text{"accaccacc"}$

Example 3：

Input ：$\text{s = "2[abc]3[cd]ef"}$
Output ：$\text{"abcabccdcdcdef"}$

Example 4：

Input ：$\text{s = "abc3[cd]xyz"}$
Output ：$\text{"abccdcdcdxyz"}$

Data range

• $\text{1}\le \text{s.length}\le \text{30}$
• $\text{s}$ Contains only lowercase English letters 、 Numbers and square brackets $\text{‘[]’}$
• $\text{s}$ Guaranteed to be valid input
• $\text{s}$ The range of values of all integers in is $\text{[1, 300]}$

Solution 1

Ideas and algorithms

The encoding string uses square brackets to represent fragments that need to be repeated , Square brackets may be nested , If nesting occurs , Then it is decoded from the inner layer to the outer layer . It is necessary to decode according to each pair of matching square brackets , To find the matching square brackets, you need to use the data structure of the stack , Therefore, the stack can be used to realize decoding .

Because the elements stored in the stack are characters , Include letters and square brackets , So you can use $\text{StringBuffer}$ Type variable instead of stack , The following is called 「 String stack 」. Except for letters and square brackets , The encoded string also contains numbers , To distinguish between numbers and non numbers , So another stack is used to store numbers , The following is called 「 Digital stack 」. Traversing the string from left to right $s$, For each type of character , The operations are as follows ：

• The current character is a number , Update the number of repetitions with the current character ;

• The current character is a letter , Then put the current character on the string stack ;

• If the character is an open square bracket , Then a number traversal ends , Put the number of repetitions on the number stack , And put the current character on the string stack ;

• If the character is a right square bracket , Then a square bracket traversal ends , Decode according to the current square bracket and the number before the square bracket , The decoding operation is as follows ：

  1. Stack the letters of the string stack in turn , Until you encounter the left square bracket , use $\text{temp}$ Store out of stack letters , Then pull the left square bracket from the string stack ;

  2. take $\text{temp}$ reverse , After reversal $\text{temp}$ The alphabetical order in the string stack is the same as that of the string stack ;

  3. The top element of the digital stack $k$ Out of the stack , be $\text{temp}$ You need to repeat in the decoded string $k$ Time , So execute $k$ The second general $\text{temp}$ String stack operation .

After the traversal , The string stack is the decoded string in the order from the bottom of the stack to the top of the stack .

Consider the following example ：$s=\text{“a3[b2[cd]]ef"}$, The length of the encoding string is $12$. The decoding operation is as follows .

Subscript $0$ The character at is a letter , Put letters on the string stack . String stack is $\text{“a"}$, The digital stack is $[]$, Where string stack replaces stack with string , Both the string stack and the number stack are at the bottom of the stack on the left , On the right is the top of the stack .

Subscript $1$ The character at is a number , Number of repetitions updated to $3$.

Subscript $2$ The character at is an open square bracket , Put the number of repetitions on the number stack , And put the left square bracket on the string stack . String stack is $\text{“a["}$, The digital stack is $[3]$.

Subscript $3$ The character at is a letter , Put letters on the string stack . String stack is $\text{“a[b"}$, The digital stack is $[3]$.

Subscript $4$ The character at is a number , Number of repetitions updated to $2$.

Subscript $5$ The character at is an open square bracket , Put the number of repetitions on the number stack , And put the left square bracket on the string stack . String stack is $\text{“a[b["}$, The digital stack is $[3,2]$.

Subscript $6$ and $7$ The characters at are all letters , Put letters on the string stack . String stack is $\text{“a[b[cd"}$, The digital stack is $[3,2]$.

Subscript $8$ The character at is a right square bracket , Do the following .

1. Put the letters of the string stack out of the stack in turn until the left square bracket is encountered , Then pull the left square bracket from the string stack ,$\text{temp}=\text{“dc"}$.

2. Reverse the letters out of the stack ,$\text{temp}=\text{“cd"}$.

3. The top element of the digital stack $k=2$ Out of the stack , perform $2$ The second general $\text{“cd"}$ String stack . String stack is $\text{“a[bcdcd"}$, The digital stack is $[3]$.

Subscript $9$ The character at is a right square bracket , Do the following .

1. Put the letters of the string stack out of the stack in turn until the left square bracket is encountered , Then pull the left square bracket from the string stack ,$\text{temp}=\text{“dcdcb"}$.

2. Reverse the letters out of the stack ,$\text{temp}=\text{“bcdcd"}$.

3. The top element of the digital stack $k=3$ Out of the stack , perform $3$ The second general $\text{“bcdcd"}$ String stack . String stack is $\text{“abcdcdbcdcdbcdcd"}$, The digital stack is $[]$.

Subscript $10$ and $11$ The characters at are all letters , Put letters on the string stack . String stack is $\text{“abcdcdbcdcdbcdcdef"}$, The digital stack is $[]$.

The decoded string is $\text{“abcdcdbcdcdbcdcdef"}$.

Code

class Solution {
    
    public String decodeString(String s) {
    
        StringBuffer sb = new StringBuffer();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int num = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
    
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
    
                num = num * 10 + c - '0';
            } else if (Character.isLetter(c)) {
    
                sb.append(c);
            } else if (c == '[') {
    
                stack.push(num);
                num = 0;
                sb.append(c);
            } else {
    
                int top = sb.length() - 1;
                StringBuffer temp = new StringBuffer();
                while (sb.charAt(top) != '[') {
    
                    temp.append(sb.charAt(top));
                    sb.deleteCharAt(top--);
                }
                sb.deleteCharAt(top--);
                temp.reverse();
                int k = stack.pop();
                for (int j = 0; j < k; j++) {
    
                    sb.append(temp);
                }
            }
        }
        return sb.toString();
    }
}

Complexity analysis

• Time complexity ：$O(n_e+n_d)$, among $n_e$ Is an encoded string $s$ The length of ,$n_d$ Is the length of the decoded string . You need to traverse the encoding string $s$ once , During decoding, you need to traverse the decoded string .

• Spatial complexity ：$O(n_d)$, among $n_d$ Is the length of the decoded string . The space complexity mainly depends on the stack space .

Solution 2

Ideas and algorithms

Solution 1 uses stack to realize decoding , You can also use recursion instead of stack .

The stack of solution one is used when encountering numbers and square brackets , The case of recursive processing is also the case of encountering numbers and square brackets . Traverse the encoded string from left to right $s$, When it comes to numbers , Get the number of repetitions , Then locate a character to the right of the left square bracket , Call recursion . The termination condition of recursion is to encounter the right square bracket , At this point, the square bracket traversal ends , Decode according to the letters in square brackets and the number of repetitions .

Code

class Solution {
    
    int index = 0;

    public String decodeString(String s) {
    
        return recurse(s).toString();
    }

    public StringBuffer recurse(String s) {
    
        StringBuffer sb = new StringBuffer();
        int length = s.length();
        while (index < length) {
    
            char c = s.charAt(index);
            if (c == ']') {
    
                return sb;
            } else if (Character.isDigit(c)) {
    
                int num = 0;
                while (index < length && Character.isDigit(s.charAt(index))) {
    
                    num = num * 10 + s.charAt(index) - '0';
                    index++;
                }
                index++;
                StringBuffer temp = recurse(s);
                for (int i = 0; i < num; i++) {
    
                    sb.append(temp);
                }
            } else {
    
                sb.append(c);
            }
            index++;
        }
        return sb;
    }
}

Complexity analysis

• Time complexity ：$O(n_e+n_d)$, among $n_e$ Is an encoded string $s$ The length of ,$n_d$ Is the length of the decoded string . You need to traverse the encoding string $s$ once , During decoding, you need to traverse the decoded string .

• Spatial complexity ：$O(n_d)$, among $n_d$ Is the length of the decoded string . The space complexity mainly depends on the stack space of recursive calls and the storage space of decoded strings $\text{StringBuffer}$ Object of type .