【Day 4 】2022-07-18 - 394. 字符串解码

[azl397985856]

394. 字符串解码

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/decode-string/

前置知识

• 栈
• 括号匹配

  题目描述

  
  给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 

示例 1：

输入：s = "3[a]2[bc]" 输出："aaabcbc" 示例 2：

输入：s = "3[a2[c]]" 输出："accaccacc" 示例 3：

输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef" 示例 4：

输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz"

[MichaelXi3]

Idea

Manipulation of Stack

Code

class Solution {
public String decodeString(String s) {
Stack<Character> stack = new Stack<>(); // Using stack to decode

    for (int i=0; i < s.length(); i++) {
        char cur = s.charAt(i);

        if (cur == ']') {
            StringBuilder sb = new StringBuilder();

            // Pop out all characters until '['
            while (!stack.isEmpty() && Character.isLetter(stack.peek())) {
                sb.insert(0, stack.pop());
            }
            String subString = sb.toString();
            stack.pop(); // Pop out '['

            // Pop out all numbers as frequency
            sb = new StringBuilder();
            while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                sb.insert(0, stack.pop());
            }
            String Freq = sb.toString();

            // Replicate substring based on frequency
            int count = Integer.valueOf(Freq);
            while (count > 0) {
                count--;
                for (char j : subString.toCharArray()) {
                    stack.push(j);
                }
            }
        } else {
            stack.push(cur);
        }
    }

    // Retrieve answer from stack
    StringBuilder ans = new StringBuilder();
    while (!stack.isEmpty()) {
        ans.insert(0, stack.pop());
    }
    return ans.toString();
}

}

# Complexity
- Time: O(N)
- Space: O(N)

[zpc7]

思路

实在没做出来, 思路太混乱了, 参考大佬的题解, 翻译了一个 TS 的版本

代码 TS

function decodeString(s: string): string {
    let stack = [], str = '', multi = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '[') {
            stack.push([multi, str]);
            str = '';
            multi = 0;
        } else if (s[i] === ']') {
            let [currentMulti, lastStr] = stack.pop();
            str = lastStr + str.repeat(currentMulti);
        } else if ('0' <= s[i] && s[i] <= '9') {
            multi = multi * 10 + Number(s[i]);
        } else {
            str += s[i]
        }
    }
    return str;
};

复杂度

时间:O(n) 空间 O(n)

[codingtrains]

思路

使用栈的压入弹出，根据右括号作为弹栈的触发。

代码

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for i in s:
            if i == ']':
                strs = ''
                repeat = ''
                while stack[-1] != '[':
                    strs = stack.pop() + strs
                stack.pop()
                while stack and stack[-1].isdigit():
                    repeat = stack.pop() + repeat
                stack.append(int(repeat) * strs)
                continue
            stack.append(i)
        return ''.join(stack)

复杂度

• 时间复杂度： O(N)
• 空间复杂度： O(N)

[hatoriMain]

思路

• 就是利用栈的特性，先把所有字符都压入栈中，遇到"]"时说明找到匹配。这个时候先将[]内的string存到一个地方。 在读完string后，开始读数字k，数字有可能不是1位，所以要用一个base和循环来读数字。 最后将 k * string压回栈中。继续匹配。最终栈内的字符串因为是反着的（出栈的时候顺序相反），所以result记得反着将栈中所有字母弹出来。

代码

class Solution {
    public String decodeString(String s) {
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ']'){
                List<Character> decodedString = new ArrayList<>();
                while(stack.peek() != '['){
                    decodedString.add(stack.pop());
                }
                stack.pop();
                int k = 0;
                int base = 1;
                while(!stack.isEmpty() && Character.isDigit(stack.peek())){
                    k = k + (stack.pop() - '0') * base;
                    base *= 10;
                }
                while(k != 0){
                    for(int j = decodedString.size() - 1; j >= 0; j--){
                        stack.push(decodedString.get(j));
                    }
                    k--;
                }
            }
            else{
                stack.push(s.charAt(i));
            }
        }

        char[] result = new char[stack.size()];
        for(int i = result.length - 1; i >= 0; i--){
            result[i] = stack.pop();
        }
        return new String(result);
    }
}

时间复杂度：O(maxK^(countK)⋅n). 空间复杂度：O(sum(maxK^(countK) ⋅n))

[laofuWF]

class Solution:
    def decodeString(self, s: str) -> str:
        stack = deque()
        count = 0
        string = ''

        for char in s:
            if char.isdigit():
                count = count * 10 + int(char)
            elif char == '[':
                stack.append(string)
                stack.append(count)
                count = 0
                string = ''
            elif char == ']':
                last_count = stack.pop()
                last_string = stack.pop()

                string = last_string + last_count * string
            else:
                string += char

        return string

[dereklisdr]

//没做出来 参考 class Solution { public String decodeString(String s) {

    int lastIndex = s.lastIndexOf('[');
    if(lastIndex<0) return s;
    int temp=lastIndex-1;
    String repeatString="";
    while(temp>=0){
        if(Character.isDigit(s.charAt(temp))){
            temp--;
        }
        else break;
    }

    int repeatNum=Integer.parseInt(s.substring(temp+1,lastIndex));

    String rpStr=s.substring(lastIndex+1, s.indexOf(']',lastIndex));
    rpStr=rpStr.repeat(repeatNum);
    s=s.replace((s.substring(temp+1,s.indexOf(']',temp+1)+1)),rpStr);
    return decodeString(s);      

}

}

[Liuxy94]

思路

利用stack实现，'['出发入栈。

代码

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        for i in s:
            if i == ']':
                strs = ''
                repeat = ''
                while stack[-1] != '[':
                    strs = stack.pop() + strs
                stack.pop()
                while stack and stack[-1].isdigit():
                    repeat = stack.pop() + repeat
                stack.append(int(repeat) * strs)
                continue
            stack.append(i)
        return ''.join(stack)

复杂度分析

时间：O(n) 空间：O(n)

[Okkband]

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        int n = s.size();
        int count = 0;
        stack<int> nums;
        stack<string> str_stk;
        for(int i=0;i<n; i++){
            char ch = s[i];
            if (ch >= '0' && ch <= '9'){
                count = count * 10 + (ch - '0');
            } else if (ch == '['){
                nums.push(count);
                str_stk.push(res);
                count = 0;
                res = "";
            } else if (ch == ']'){
                for(int j=0; j<nums.top(); j++){
                    str_stk.top() += res;
                }
                nums.pop();
                res = str_stk.top();
                str_stk.pop();
            } else {
                res += ch;
            }
        }
        return res;

    }
};

时间复杂度：O(n) 空间复杂度：O(n)

[flaming-cl]

Java

class Solution {
    public String decodeString(String s) {
        Stack<Integer> tStack = new Stack<>();
        Stack<String> sStack = new Stack<>();
        String temp = "";
        int times = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                times = times * 10 + c - '0';
                continue;
            }
            if (c == '[') {
                sStack.push(temp);
                tStack.push(times);
                temp = "";
                times = 0;
                continue;
            }
            if (c == ']') {
                temp = sStack.pop() + temp.repeat(tStack.pop());
                continue;
            }
            temp += c;
        }
        return temp;
    }
}

T: O(N) S: O(N)

[xixiao51]

Idea

Use 2 stacks one to store all the integer k and one to store all the decoded strings.

Code

class Solution {
    public String decodeString(String s) {
        StringBuilder str = new StringBuilder();
        Stack<Integer> num = new Stack<>();
        Stack<StringBuilder> letters = new Stack<>();
        int k = 0;
        for(char c: s.toCharArray()) {
            if(Character.isDigit(c)) {
                k = k * 10 + (c - '0');
            } else if(c == '[') {
                num.push(k);
                k = 0;
                letters.push(str);
                str = new StringBuilder();
            } else if(c == ']') {
                StringBuilder temp = letters.pop();
                for(int i = num.pop(); i > 0; i--) {
                    temp.append(str);
                }
                str = temp;
            } else {
                str.append(c);
            }
        }

        return str.toString();
    }
}

Complexity Analysis

• Time complexity: O(kn)
• Space complexity: O(num(k) + num(char))

[joeymoso]

class Solution:
    def decodeString(self, s: str) -> str:

        stack = []

        for c in s:
            if c == ']':
                cur_str = ''
                cur_count = ''
                # get repeat string
                while stack and stack[-1] != '[':
                    cur_str = stack.pop() + cur_str
                # pop '['
                stack.pop()
                # get repeat count
                while stack and stack[-1].isnumeric():
                    cur_count = stack.pop() + cur_count
                # push back to the stack
                stack.append(int(cur_count) * cur_str)

            else:
                stack.append(c)

        return ''.join(stack)

• Time: O(n)
• Space: O(n)

[lsunxh]

class Solution(object): def getNum(self, s, rInd): res = 0 place = 0 while rInd >= 0 and s[rInd].isnumeric(): res += 10*placeint(s[rInd]) place += 1 rInd -= 1 return res, rInd + 1

def decodeString(self, s):
    """
    :type s: str
    :rtype: str
    """
    # base case: "a", "[a]", "3[a]"
    # recursive case: "3[3[a]]"
    left = []
    i = 0
    disFromLast = len(s)
    while disFromLast > 0:
        i = len(s) - disFromLast
        if s[i] == "[":
            left.append(i)
        elif s[i] == "]":
            # get the last left bracket
            lastLeft = left[-1]
            left = left[:-1]
            curStr = s[lastLeft+1:i]
            if s[lastLeft-1].isnumeric():
                num, newInd = self.getNum(s, lastLeft-1)
            else:
                num, newInd = 1, i
            # update s
            if i == len(s)-1:
                s = s[:newInd] + num * s[lastLeft+1:i]
            else:
                s = s[:newInd] + num * s[lastLeft+1:i] + s[i+1:]
        # updating i depends on length change in s
        disFromLast -= 1
    return s

[richypang]

思路

判断遇到的是字符串还是数字还是括号，分别作不同处理

代码

#
class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, times = [], "", 0
        for c in s:
            if c == '[':
                stack.append([times, res])
                res, times = "", 0
            elif c == ']':
                cur_times, last_res = stack.pop()
                res = last_res + cur_times * res
            elif '0' <= c <= '9':
                #判断多位数字情况
                times =  times * 10 + int(c)            
            else:
                res += c
        return res

复杂度

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[ashleyyma6]

Idea

1. Traverse s
   1. push number to stack num
   2. push [ & characters to stack char, until meet ]
   3. when meet ], pop stack char & add characters together until meet [
   4. pop the stack num, decode characters, push result back to stack char
2. return stack char content

   Code

def decodeString(self, s):
        num = []
        char = []
        i = 0
        while i < len(s):
            if s[i].isdigit():
                n = ""
                while(s[i].isdigit()):
                    n+=s[i]
                    i+=1
                num.append(int(n))
            elif s[i] == ']':
                tmp = ""
                while char[-1]!='[':
                    tmp = char.pop()+tmp
                char.pop()
                tmp = tmp*num.pop()
                char.append(tmp)
                i+=1
            else:
                char.append(s[i])
                i+=1
        res = ""
        while len(char)>0:
            res = char.pop()+res
        return res

Complexity Analysis

• Time Complexity:O(n)+O(n)+O(n)=O(n)
• Space Complexity:O(n)

[uyplayer]

LC 394. 字符串解码

Leetcode连接

• 分支方法

分支方法

本题中可能出现括号嵌套的情况，比如 2[a2[bc]]，这种情况下我们可以先转化成 2[abcbc]，在转化成 abcbcabcbc。我们可以把字母、数字和括号看成是独立的 TOKEN，并用栈来维护这些 TOKEN。具体的做法是，遍历这个栈：

• 如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
• 如果当前的字符为字母或者左括号，直接进栈
• 如果当前的字符为右括号，开始出栈，一直到左括号出栈，出栈序列反转后拼接成一个字符串，此时取出栈顶的数字（此时栈顶一定是数字，想想为什么？），就是这个字符串应该出现的次数，我们根据这个次数和字符串构造出新的字符串并进栈

Golang 代码

func decodeString(s string) string {
    // 栈
    stk := []string{}
    ptr := 0
    for ptr < len(s) {
        cur := s[ptr]
        // 如果是数字进栈
        if cur >= '0' && cur <= '9' {
            digits := getDigits(s, &ptr)
            stk = append(stk, digits)
            // 如果是字母或者左口号进栈
        } else if (cur >= 'a' && cur <= 'z' || cur >= 'A' && cur <= 'Z') || cur == '[' {
            stk = append(stk, string(cur))
            // 下边往前走一步
            ptr++
        } else {
            // 遇到右括号
            ptr++
            sub := []string{}
            for stk[len(stk)-1] != "[" {
                // 出栈
                sub = append(sub, stk[len(stk)-1])
                // 更新str
                stk = stk[:len(stk)-1]
            }
            // 反转 
            for i := 0; i < len(sub)/2; i++ {
                sub[i], sub[len(sub)-i-1] = sub[len(sub)-i-1], sub[i]
            }
            //   stk[len(stk)-1] != "[" 已经碰到右括号']'，去掉它
            stk = stk[:len(stk)-1]
            // 出栈 的时候数字
            repTime, _ := strconv.Atoi(stk[len(stk)-1])
            // 更新栈
            stk = stk[:len(stk)-1]
            // 重复
            t := strings.Repeat(getString(sub), repTime)
            // 添加到数组中
            stk = append(stk, t)
        }
    }
    return getString(stk)
}

func getDigits(s string, ptr *int) string {
    ret := ""
    for ; s[*ptr] >= '0' && s[*ptr] <= '9'; *ptr++ {
        ret += string(s[*ptr])
    }
    return ret
}

func getString(v []string) string {
    ret := ""
    for _, s := range v {
        ret += s
    }
    return ret
}

复杂度分析

• 时间复杂度： 记解码后得出的字符串长度为 SS，除了遍历一次原字符串 ss，我们还需要将解码后的字符串中的每个字符都入栈，并最终拼接进答案中，故渐进时间复杂度为O(S+∣s∣)，即 O(S)
• 空间复杂度：记解码后得出的字符串长度为 SS，这里用栈维护 TOKEN，栈的总大小最终与 SS 相同，故渐进空间复杂度为 O(S)。

[yopming]

思路

使用两个stack，一个存数字，一个存之前已经decode完成的部分。 由于input是valid，只存在如下4中情况

• digit: 存入stack1。需要注意超过9的数字，需要先暂存。
• alphabet: 拼接到局部变量
• [: 把数字和已经之前已经deocde的string放入各自stack
• ]: 此时当前括号内的string还没有被push到stack2，而需要重复的数字已经被push了，所以要从stack1取top值。然后需要把之前decode完成的部分取出来，拼接当前括号的内容。最后要把拼接好的string赋予局部变量，以备下一次push时候所用。

代码

class Solution {
public:
    string decodeString(string s) {
      if (s.empty()) {
        return s;
      }

      std::string k;    // temp
      std::string str;  // temp
      std::stack<int> countStack;
      std::stack<std::string> stringStack;

      for (auto& ch: s) {
        if (isdigit(ch)) {
          k += ch;
        } else if (isalpha(ch)) {
          str += ch;
        } else if (ch == '[') {
          countStack.push(std::stoi(k));
          stringStack.push(str);
          k = "";
          str = "";
        } else if (ch == ']') {
          // get previously decoded, such as in 3[a]2[bc]
          // second '[' push 'aaa' to stack, get them now
          std::string decodedString = stringStack.top();
          stringStack.pop();

          // str is not pushed to stack yet, but times is already pushed
          for (int i = 0; i < countStack.top(); i++) {
            decodedString += str;
          }
          countStack.pop();

          // remember the local variable
          str = decodedString;
        }
      }

      return str;
    }
};

复杂度分析 Assume $N$ is the length of input string.

• 时间复杂度 $O(kN)$ such that $k$ is the maximum of digits in the input string.
• 空间复杂度 $O(N)$ or $O(m+n)$ such that $m$ is the number of digits, $n$ is the number of alphabets and $m+n <= N$ since the existence of brackets.

[Whisht]

思路

将每个字符入栈，当遇到']'时出栈，直至遇到'['，'['前的所有数字出栈，即为k，将出栈得到的括号内所有字符重复 k次，入栈。

代码

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res = ""
        for i in s:
            if i == "]":
                tmp = stack.pop()
                ch = ""
                while tmp != "[":
                    ch = tmp + ch
                    tmp = stack.pop()
                time = 0
                c = 0
                while stack and stack[-1].isdigit():
                    t1 = stack.pop()
                    time += int(t1) * 10 ** c
                    c+=1
                ch = ch * time
                stack.append(ch)
            else:
                stack.append(i)
        if stack:
            res = "".join(i for i in stack)
        return res

复杂度

• 时间复杂度：$O(N)$，需要遍历一遍字符
• 空间复杂度：$O(N)$，主要来源于栈

[wsmmxmm]

基本信息

题号&链接

394. 字符串解码

截图题面

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"

UMPIRE

U-nderstand

• s 中所有整数的取值范围为 [1, 300]

有可能不是一位数

M-atch

放到栈里，遇到‘]’的话，往前找 ‘[’ 和 k，找到后重复k次，并放回栈内（以防止 [] 嵌套）

复杂度

空间算O(n)

时间摆烂不会算 O(n^2)?

Code

做了好久哦，以及写的好麻烦，运行的好慢哦。

我要看看题解

class Solution {
    public String decodeString(String s) {

        if(s.length() <= 3) return s;

        int i = 0;
        char[] c = s.toCharArray();
        StringBuffer sb = new StringBuffer();
        Deque<Character> deque = new ArrayDeque<>();

        while(i < c.length){

            if(c[i] == ']'){
                int k = 0;
                char temp = deque.pollLast();
                StringBuffer sbTemp = new StringBuffer();
                while (temp != '['){
                    sbTemp.append(temp);
                    temp = deque.pollLast();
                }
                char tempk = deque.peekLast();
                int count = 0;
                while(tempk - '0' <= 9 && tempk - '0' >= 0 && !deque.isEmpty()){
                    k += Math.pow(10,count) * ( deque.pollLast() - '0');
                    //System.out.println("k=:"+k+";tempk=:"+tempk);
                    if (!deque.isEmpty()) {
                        tempk = deque.peekLast();
                        count++;
                    }

                }
                sbTemp.reverse();
                char[] sbChar = sbTemp.toString().toCharArray();
                while(k > 0){
                    //System.out.println("sbTemp=:"+sbTemp.toString()+";deque=:"+deque.toString());
                    for(char cT: sbChar){
                        deque.addLast(cT);
                    }
                    k--;
                }

            }else{
                deque.addLast(c[i]);
            }
            i++;

        }
        while(!deque.isEmpty()){
            sb.append(deque.pollFirst());
        }
        return sb.toString();

    }
}

害

[Erikahuang]

思路

"在栈里面每次存储两部分信息：左括号前的字符串, 左括号前的数字, 比如abc3[def], 当遇到第一个左括号的时候，压入栈中的是("abc", 3), 然后遍历括号里面的字符串def, 当遇到右括号的时候, 从栈里面弹出一个元素(s1, n1), 得到新的字符串为s1+n1*"def", 也就是abcdefdefdef。对于括号里面嵌套的情况也是同样处理方式。" 左括号触发压栈，右括号触发弹出。

代码

class Solution:
    def decodeString(self, s: str) -> str:
        stack = deque()
        cnt = 0
        string = ''

        for char in s:
            if char.isdigit():
                cnt = int(char) + cnt*10
                continue
            elif char == '[':
                stack.append((string, cnt))
                string = ''
                cnt = 0
            elif char == ']':
                tmp = stack.pop()
                string = tmp[0] + tmp[1]*string
            else:
                string +=char

        return string

复杂度

• 时间复杂度: O(n)
• 空间复杂度:O(n)

[shiyishuoshuo]

code:

public String decodeString(String s) {
        int n = s.length();
        Deque<Character> stack = new LinkedList<>();
        char[] ss = s.toCharArray();
        for (char c : ss) {
            if (c != ']') {
                stack.push(c);
            } else {
                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty() && Character.isLetter(stack.peek())) {
                    sb.insert(0, stack.pop());
                }
                stack.pop(); // skip :[
                int num = 0;
                int base = 1;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    num  += (stack.pop() - '0') * base;
                    base *= 10;
                }
                String str = sb.toString();
                 String temp = "";
                while (num !=0){
                    temp += str;
                    num--;
                }
                for (Character t : temp.toCharArray()){
                    stack.push(t);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (char c : stack) {
            sb.insert(0, c);
        }
        return sb.toString();
    }

time: O(n) space: O(n)

[wzasd]

思路

与之前的匹配字符串有点像，这里采用入栈的方式，分为三种情况

1. 数字入栈，这里要对连续数字进行处理
2. 字母还有“[”括号入栈
3. 遇到“]”括号出栈，同时截取第二步括号之前的字符

弹出"["括号字符，获取重复的次数，处理这些字符串就可以了。

代码

    int curIndex;
    public String decodeString(String s) {
        LinkedList<String> ans = new LinkedList<>();
        curIndex = 0;
        while (curIndex < s.length()) {
            char c = s.charAt(curIndex);
            if (Character.isDigit(c)) {
                String strDigit = getDigits(s);
                ans.addLast(strDigit);
            } else if (Character.isLetter(c) || c == '[') {
                ans.addLast(String.valueOf(s.charAt(curIndex++)));
            } else {
                curIndex++;
                LinkedList<String> subStr = new LinkedList<>();
                while (!ans.peekLast().equals("[")){
                    subStr.addLast(ans.removeLast());
                }
                ans.removeLast();
                Collections.reverse(subStr);
                Integer repeatTimes = Integer.parseInt(ans.removeLast());
                StringBuffer sb = new StringBuffer();
                String o = getString(subStr);
                while (repeatTimes-- > 0 ){
                    sb.append(o);
                }
                ans.addLast(sb.toString());
            }
        }
        return getString(ans);
    }

    public String getDigits(String s) {
        StringBuffer sb = new StringBuffer();
        while (Character.isDigit(s.charAt(curIndex))){
            sb.append(s.charAt(curIndex++));
        }
        return sb.toString();
    }

    public String getString(LinkedList<String> ll) {
        StringBuffer ans = new StringBuffer();
        for (String s :
                ll) {
            ans.append(s);
        }
        return ans.toString();
    }

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.decodeString("3[a]2[bc]"));
    }

复杂度分析

• 时间复杂度：O(N)，其中 N 为字符串长度。
• 空间复杂度：O(N)

[suukii]

• Time: $O(N)$. N is the length of the decoded string
• Space: $(O(N)$. N is the length of the decoded string. This is the space used by the tokens stack.

class Solution {
public:
    string decodeString(string s) {
        stack<string> tokens;

        for (char c : s) {
            if (c != ']') {
                tokens.push(string(1, c));
                continue;
            }

            // get the repeat patern
            // everything after "["
            string p;
            while (!tokens.empty() && tokens.top() != "[") {
                p += tokens.top();
                tokens.pop();
            }
            // pop out the "["
            tokens.pop();

            // get the repeat number
            // which comes right before the "["
            string num;
            while (!tokens.empty() && isNumber(tokens.top())) {
                num = tokens.top() + num;
                tokens.pop();
            }

            // repeat the pattern string and put it back to the stack
            tokens.push(repeat(stoi(num), p));
        }

        return join(tokens);
    }
private:
    bool isNumber(const std::string& s) {
        auto it = s.begin();
        while (it != s.end() && std::isdigit(*it)) ++it;
        return !s.empty() && it == s.end();
    }

    string repeat(int k, string s) {
        string res;
        while (k) {
            res += s;
            k--;
        }
        return res;
    }

    string join(stack<string> stk) {
        string res;
        while (!stk.empty()) {
            res += stk.top();
            stk.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Recursion version

class Solution {
public:
    string decodeString(string s) {
        return decodeString(s, 0).first;
    }
private:
    pair<string, int> decodeString(const string& s, int i) {
        string p, num;
        while (i < s.size()) {
            if (s[i] == '[') {
                // begin recursion
                auto [str, next_i] = decodeString(s, i + 1);
                p += repeat(stoi(num), str);
                num = "";
                i = next_i;
            } else if (s[i] == ']') {
                return make_pair(p, i + 1);
            } else if (isdigit(s[i])) {
                num += s[i++];
            } else {
                p += s[i++];
            }
        }
        return make_pair(p, i + 1);
    }

    string repeat(int k, string s) {
        string res;
        while (k) {
            res += s;
            k--;
        }
        return res;
    }
};

[nehchsuy]

思路:

不使用dfs一遍遍历 两个栈, 一个压入乘数, 一个压入字符串

预处理 给字符串两边加上"[" 和 "]" 设原乘数为1

遇到"[" 数字入栈, 乘数重新设为0, 将"[" 作为字符串mark压入字符栈 遇到 lowercase字母, 如果是第一个字母, 创造新字符串, 不然更新最近字符串 遇到乘数, 更新乘数 遇到 "]" 把所有 前一个 "["之前的字符串合并 (字符串出栈) x 最近的乘数 (乘数出栈) 再重新压入字符串栈中

最后乘数栈为空, 字符串栈中唯一一个元素就是答案

代码

class Solution:
    def decodeString(self, s: str) -> str:
        strs = []
        nums = []

        num = 1
        s = "[" + s + "]"

        for char in s:
            if char == "[":
                strs.append("[")
                nums.append(num)
                num = 0
            elif char in "0123456789":
                num = num * 10 + int(char)
            elif char in "abcdefghijklmnopqrstuvwxyz":
                if strs[-1] == "[":
                    strs.append(char)
                else:
                    strs[-1] = strs[-1] + char
            else:
                temp = ""
                while strs[-1] != "[":
                    temp = strs[-1] + temp
                    strs.pop()
                times = nums.pop()
                strs.pop()
                strs.append(temp * times)

        return strs[-1]

复杂度

时间复杂度: O(n) n 为字符串内所有元素个数 空间复杂度: O(n) n 为字符串内所有元素个数

[caterpillar-0]

思路

用栈匹配括号，分别处理数字，字母和括号

代码

class Solution {
public:
    string GetDigit(const string& s,size_t& ptr){
        string ret="";
        //因为数字不止一位
        while(isdigit(s[ptr])){
            ret.push_back(s[ptr++]);//对ptr有改动，因此需要&
        }
        return ret;
    }
    string GetString(vector<string>& sub){
        string temp="";
        for(string& s:sub){
            temp+=s;
        }
        return temp;
    }
    string decodeString(string s) {
        vector<string>myvec;
        size_t ptr=0;
        while(ptr<s.size()){
            char ch=s[ptr];
            //1、处理数字
            if(isdigit(ch))myvec.push_back(GetDigit(s,ptr));
            //2、处理字母
            else if(isalpha(ch) || ch=='[')myvec.push_back(string(1,s[ptr++]));
            //3、处理']'
            else{
                ++ptr;
                vector<string>sub;
                while(myvec.back()!="["){
                    sub.push_back(myvec.back());
                    myvec.pop_back();
                }
                myvec.pop_back();
                reverse(sub.begin(),sub.end());
                string temp=GetString(sub);
                int times=stoi(myvec.back());
                myvec.pop_back();
                string temp_1;
                while(times--){
                    temp_1+=temp;
                }
                myvec.push_back(temp_1);
            }
        }
        return GetString(myvec);
    }
};

复杂度分析

• 时间复杂度：o(n)
• 空间复杂度：o(n)

[UCASHurui]

思路

---

用一个栈保存遇到的字符，当遇到’]’时开始弹出，直到’[’时当前字符串获取完毕，开始获取重复的次数n，然后将字符串重复n次，并将重复n次后的字符串重新压入栈，如此循环。最终将栈中所有字符串和并后返回

代码

---

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for i in range(len(s)):
            char = s[i]
            if char != ']':
                stack.append(char)
            else:
                tmp_str = ''
                while stack[-1] != '[':
                    tmp_str = stack.pop(-1) + tmp_str
                stack.pop(-1)
                num_str = ''
                while stack and stack[-1].isdigit():
                    num_str = stack.pop(-1) + num_str
                tmp_res = tmp_str * int(num_str)
                stack.append(tmp_res)
        return ''.join(stack)

复杂度分析

---

• 时间复杂度：O(N)， N是字符串解码后的长度
• 空间复杂度：O(N)

[xxoojs]

代码

---

/**
 * @param {string} s
 * @return {string}
*/
const numReg = /[0-9]/;
const charReg = /[a-z]/;
var decodeString = function(s) {
    let i = 0,
        len = s.length,
        stack = [],
        times = '',
        ret = '';
    while (i < len) {
        const char = s[i];
        if (charReg.test(char)) {
            const last = stack[stack.length - 1];
            if (last) {
                last.letters += char;
            } else {
                ret += char;
            }
        }
        if (numReg.test(char)) {
            times += char;
        }
        if (char === '[') {
            stack.push({
                times,
                letters: ''
            });
            times = '';
        }
        if (char === ']') {
            let fragment = stack.pop();
            let _times = Number(fragment.times) || 1;
            fragment = fragment.letters.repeat(_times);

            const last = stack[stack.length - 1];
            if (last) {
                last.letters += fragment;
            } else {
                ret += fragment;
            }
        }
        ++i;
    }
    return ret;
};

[Ye2222]

思路

利用栈先进后出的特性，进行括号匹配，将生成的字符一并压入栈中进行处理

Code

int power(int x, int k) {
    int pow = 1;
    for(int i = 0; i < k; i++) {
        pow *= 10;
    }
    return x * pow;
}

string decodeString(string s) {
    stack <char> stk;
    int n = s.size();
    bool isNum =true;
    string s1 = "";
    int i = 1;
    stk.push(s[0]);
    while(!stk.empty() && i < n) {
        if (s[i] == ']') {
            isNum = true;
            // 重复的字符
            while(stk.top() != '[') {
                char c = stk.top();
                stk.pop();
                s1.insert(0, 1, c);
            }
            // 弹出左括号
            stk.pop();
            // 重复的次数
            int count = 0, pow = 0;
            while(!stk.empty() && stk.top() - '0' <= 9 && stk.top() - '0' >= 0) {
                count += power(stk.top()-'0', pow);
                pow++;
                stk.pop();
            }
            // 重复压入栈中
            while(count > 0) {
                for(int i = 0; i < s1.size(); i++) {
                    stk.push(s1[i]);
                }
                count--;
            }
            s1 = "";
        }
        else if(isNum && s[i] != '[') {
            stk.push(s[i]);
        } 
        else if (s[i] == '[') {
            stk.push(s[i]);
            isNum = false;
        }
        else{
            stk.push(s[i]);
        }
        i++;
    }

    string res;
    while(!stk.empty()) {
        res.insert(0, 1, stk.top());
        stk.pop();
    }
    return res;
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[LiquanLuo]

Solution:

data structure: stack to store

1. loop whole string\ 1.1. if digit, letters or [ push to stack\ 1.2. if ] pop until find [, \       then find all the digit before, convert to int\       int * [string], push back to stack
2. when we running out of s, pop out all the string from the stack and return

Code:

class Solution {
public:
    string decodeString(string s) {
        stack<char> st;
        for (auto c : s) {
            if (c == ']') {
                auto str = find_str(st);
                auto repeat = find_num(st);
                string repeated_str;
                while (repeat > 0) {
                    repeated_str += str;
                    --repeat;
                }
                // cout << "repeated_str" << repeated_str << endl;
                for (auto repeated_char : repeated_str) {
                    st.push(repeated_char);
                }
            }
            else {
                st.push(c);
            }
        }

        string result;
        while (!st.empty()) {
            auto c = st.top();
            result += c;
            st.pop();
        }
        reverse(result.begin(), result.end());

        return result;

    }

private:
    string find_str(stack<char>& st) {
        string str;
        while (!st.empty()) {
            auto c = st.top();
            if (c == '[') {
                st.pop();
                break;
            }
            else{
                str += c;
                st.pop();
            }
        }

        reverse(str.begin(), str.end());
        // cout << "find str" << str << endl;
        return str;
    }

    int find_num(stack<char>& st) {
        string num_str;
        while (!st.empty()) {
            auto c = st.top();
            if (!isdigit(c)) {
                break;
            }
            else{
                num_str += c;
                st.pop();
            }
        }

        reverse(num_str.begin(), num_str.end());
        // cout << "find num_str" << num_str << endl;
        int num = stoi(num_str);
        return num;
    }

};

complexity analysis

• Time：O(N)，
• Space：O(N)

[Tlntin]

• 题目连接

  代码

  
  // CopyRight 2022
  #include <iostream>
  #include <string>
  #include <vector>

using std::string;

class Solution { public: string decodeString(const string & s) { std::string result; std::vector stack1; std::vector temp_stack; int temp_num; int p; std::string temp_str; for (const char & c : s) { if (c != ']') { stack1.emplace_back(c); } else { // 出栈取字符串 while(stack1.back() != '[') { temp_stack.emplace_back(stack1.back()); stack1.pop_back(); } // 去除 "[" stack1.pop_back(); // 出栈取数组 p = 1; temp_num = 0; while((!stack1.empty()) && ('0' <= stack1.back()) && (stack1.back() <= '9')) { temp_num += p (stack1.back() - '0'); stack1.pop_back(); p = 10; } // 获取当前临时字符串(记得反向) temp_str.resize(temp_stack.size()); for (int i = 0; i < temp_stack.size(); ++i) { temp_str[temp_stack.size() -1 - i] = temp_stack[i]; } // std::cout << temp_num << "\t" << temp_str << "\t" << std::endl; // 成果插入stack1(这里貌似可以优化, 因为会导致后续重复循环, 但是要是不插入，如何做到数据对齐？) for (int i =0; i < temp_num; ++i) { stack1.insert(stack1.end(), temp_str.begin(), temp_str.end()); } //清空temp_stack temp_stack.clear(); temp_str.clear(); } } // 打印最终结果 result.resize(stack1.size()); for (int i = 0; i < stack1.size(); ++i) { result[i] = stack1[i]; } return std::move(result); } };

int main() { Solution s; std::string res = s.decodeString("3[a2[c]]"); std::cout << res << std::endl; std::cout << s.decodeString("10[a]2[bc]") << std::endl; std::cout << s.decodeString("2[abc]3[cd]ef") << std::endl; std::cout << s.decodeString("abc3[cd]xyz") << std::endl; }

### 复杂度
- 时间：$O(n^2)$
- 空间: $O(n)$

### 结果
![c61fb2e7d9c552d97327037bad88d5a3.png](https://s2.loli.net/2022/07/18/Y14wDcpRWVGiUMH.png)

### 优化
- 成果不插入到原stack，减少遍历次数与空间占用(那数据如何对齐？)
- 中间不加入temp_str，减少空间占用（但是会增加更多遍历次数，不太划算）
- 所以还是放弃了。

[cytrue]

//用栈来解决 //数字和字母都进栈，当碰到】号时，就开始循环重复生成字符串，生完后再反转

class Solution { int ptr;

public String decodeString(String s) {
    LinkedList<String> stk = new LinkedList<String>();
    ptr = 0;

    while (ptr < s.length()) {
        char cur = s.charAt(ptr);
        if (Character.isDigit(cur)) {
            // 获取一个数字并进栈
            String digits = getDigits(s);
            stk.addLast(digits);
        } else if (Character.isLetter(cur) || cur == '[') {
            // 获取一个字母并进栈
            stk.addLast(String.valueOf(s.charAt(ptr++))); 
        } else {
            ++ptr;
            LinkedList<String> sub = new LinkedList<String>();
            while (!"[".equals(stk.peekLast())) {
                sub.addLast(stk.removeLast());
            }
            Collections.reverse(sub);
            // 左括号出栈
            stk.removeLast();
            // 此时栈顶为当前 sub 对应的字符串应该出现的次数
            int repTime = Integer.parseInt(stk.removeLast());
            StringBuffer t = new StringBuffer();
            String o = getString(sub);
            // 构造字符串
            while (repTime-- > 0) {
                t.append(o);
            }
            // 将构造好的字符串入栈
            stk.addLast(t.toString());
        }
    }

    return getString(stk);
}

public String getDigits(String s) {
    StringBuffer ret = new StringBuffer();
    while (Character.isDigit(s.charAt(ptr))) {
        ret.append(s.charAt(ptr++));
    }
    return ret.toString();
}

public String getString(LinkedList<String> v) {
    StringBuffer ret = new StringBuffer();
    for (String s : v) {
        ret.append(s);
    }
    return ret.toString();
}

}

[kiirii4]

思路

使用递归，遇到数字，记录至multi，遇到字母，将其加入本层的字符串中，遇到"["进入新的一层递归，并将下一层返回的字符串重复multi次加至本层的字符串中，遇到“]”返回本层字符串

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return dfs(s, i);
    }

    string dfs(string &s, int &i){
        int multi = 0;
        string res = "";
        for(; i < s.size(); ++i){
            if('0' <= s[i] && s[i] <= '9')
                multi = multi * 10 + (s[i] - '0');
            else if(s[i] == '['){
                string temp = dfs(s ,++i);
                while(multi != 0){
                    res += temp;
                    --multi;
                }
            }
            else if(s[i] == ']')
                return res;
            else
                res += s[i];
        }
        return res;
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$ 在递归的过程中索引是更新的，一次遍历
• 空间复杂度：$O(n)$ 最坏情况下（如：3[3[3[a]]]）递归次数为(n-4)/3，需要线性空间

[luckyTWJ]

思路

递归搜索

class Solution {
     int i  = 0;
    public String decodeString(String s) {

        return dfs(s,0);
    }
   String dfs(String s, int curr) {

        StringBuilder sb = new StringBuilder();
        //i设置成全局变量
        for ( i = curr; i < s.length(); i++) {
            if (Character.isDigit(s.charAt(i))) {
                int num = 0, k = i;
                //拼数字
                while (k < s.length() && Character.isDigit(s.charAt(k))) {
                    num = 10 * num + (s.charAt(k) - '0');
                    k++;
                }
                i = k;
                if (s.charAt(i) == '[') {
                    //这里dfs返回时 i已经更新了（来到了‘]’的位置了），
                    //如果还使用当前局部变量会造成重复，所以需要全局变量 跳出当前循环
                    String a = dfs(s, i + 1);
                    //拼串
                    for (int b = 0; b < num; b++)
                            sb.append(a);
                }

            } else if (s.charAt(i) == ']') { 
                return sb.toString();
            } else
                sb.append(s.charAt(i));
        }
        return sb.toString();

    }
}

[lbc546]

Use stack to complete the decode within each pairs of bracket, pushing the decoded string in the brackets to the stack again.

Python solution

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        ans = ""

        for c in s:
            # Not closing brackets, push into stack
            if c != ']':
                stack.append(c)
            else:
                # Otherwise, first get the characters within the brackets
                r = ""
                while stack and stack[-1] != '[':
                    # reverse the order
                    r = stack.pop() + r

                # pop the opening bracket out
                stack.pop()

                # get the number of times to repeat
                n = ""
                while stack and stack[-1].isnumeric():
                    f = stack.pop()
                    # reverse order
                    n = f + n

                # push the cleaned and decoded string into the stack
                stack.append(r * int(n))
        for c in stack:
            ans += c

        return ans

Complexity O(n)

[lzyxts]

Idea

• 从s的第一位读起，根据读到的char进行不同操作：
• 如果碰到数字则记录次数，如果碰到字母则记下并移到下一位，如果 ==[ 则记录读过的string和次数放进stack，如果 ==] 则stack.pop() 补充一次[]的完整string
• 当 [ ] 次数相同时，一个完整的string已经完成，加进res中

Code

class Solution:
    def decodeString(self, s: str) -> str:
        res = ''
        l= 0
        stack = []
        cur = ''
        i = 0
        freq = 0

        while i < len(s):
            if s[i] == '[':
                l += 1
                stack.append([cur,freq])
                cur = ''
                freq = 0
                i+=1
            elif s[i].isdigit():
                while s[i].isdigit():
                    freq = freq*10+int(s[i])
                    i+=1
            elif s[i] == ']':
                l -=1
                pre, num = stack.pop()
                cur = pre + cur*num
                if l == 0:
                    res += cur
                    cur = ''
                i+=1

            elif s[i].isalpha():
                cur += s[i]
                i+=1

        return res+cur

Complexity

• Time：O(N)
• Space：O(N)

[Serena9]

思路

遍历字符串，如果遇到‘【’，数字和字母，全部存到栈中；如果遇到‘】’，开始出栈，将‘【’之前的字母全都出栈并存到临时字符串中，然后数字部分出栈并存到次数字符串中，最后计算出重复的字符串并入栈

代码

class Solution:
    def decodeString(self, s: str) -> str:
        ans = []
        for c in s:
            if c == ']':
                string = ''
                count = ''
                while ans and ans[-1] != '[':
                    string = ans.pop() + string
                ans.pop()
                while ans and ans[-1].isnumeric():
                    count = ans.pop() + count
                ans.append(string * int(count))
            else:
                ans.append(c)
        return ''.join(ans)

复杂度分析

• 时间复杂度：O（n）
• 空间复杂度：O（n）

[HackBL]

判断几种可能性，对不同可能性进行单独判断

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();

        Stack<String> sbStack = new Stack<>();
        Stack<Integer> digitStack = new Stack<>();
        int idx = 0;
        while (idx < s.length()) {
            char c = s.charAt(idx);
            if (Character.isDigit(c)) {
                int freq = 0;
                while(Character.isDigit(s.charAt(idx))) {
                    freq = freq * 10 + s.charAt(idx) - '0';
                    idx++;
                }

                digitStack.push(freq);
            } else if (c == '[') {
                sbStack.push(res.toString());
                res = new StringBuilder();
                idx++;
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                tmp.append(sbStack.pop());

                int freq = digitStack.pop();

                for (int j = 0; j < freq; j++) {
                    tmp.append(res.toString());
                }

                res = tmp;
                idx++;
            } else {
                res.append(c);
                idx++;
            }
        }

        return res.toString();
    }
}

Time: O(n) Space: O(n)

[frankelzeng]

Idea

Use a single stack to track the input

Python Code

import collections
class Solution:
    def decodeString(self, s: str) -> str:
        stk = collections.deque()
        for idx,c in enumerate(s):
            if c == ']':
                curr = stk.pop()
                temp = ""
                while curr.isalpha():
                    temp = curr + temp
                    curr = stk.pop()
                temp_num = ""
                if curr == '[':
                    curr = stk.pop()
                # print("curr=",curr)
                while curr.isdigit():
                    temp_num = curr + temp_num
                    if stk and stk[-1].isdigit():
                        curr = stk.pop()
                    else:
                        curr = ""
                num = int(temp_num)
                for _ in range(num):
                    for t in temp:
                        stk.append(t)
            else:
                stk.append(c)
            # print(stk)
        return "".join(list(stk))

Complexity

Time: O(max(k) n) Space: O(max(k) n)

[thinkfurther]

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        for c in s:
            if c == ']':
                num = ''
                cur_s = ''
                while stack[-1] != '[':
                    cur_s = stack.pop() + cur_s
                stack.pop()
                while stack and stack[-1].isdigit():
                    num = stack.pop() + num
                stack.append(int(num) * cur_s)
            else:
                stack.append(c)
        return ''.join(stack)

时间复杂度：O(n) 空间复杂度：O(n)

[zzzkaiNS]

思路

按规则 dfs 结果

代码

class Solution {
public:
    string decodeString(string s) {
        int u = 0;
        return dfs(s, u);
    }

    string dfs(string& s, int& u) {
        string res;
        while (u < s.size() && s[u] != ']') {
            if (s[u] >= 'a' && s[u] <= 'z') res += s[u ++];
            else if (s[u] >= '0' && s[u] <= '9') {
                int k = u;
                while (s[k] >= '0' && s[k] <= '9') k ++;
                int t = stoi(s.substr(u, k - u));
                u = k + 1;
                string sa = dfs(s, u);
                u ++;
                while (t --) res += sa;
            }
        }
        return res;
    }
};

[elaineKuo]

思路

利用栈的方式；当遇到数字时，存入栈。 遇到‘【’时，记录前面的字符结果，然后入栈；遇到‘】’时，数字和上次的str同时出栈，然后计算本次的字符串的叠加。

代码

var decodeString = function(s) {
    let numStack = [];
    let strStack = [];
    let num =0;
    let res = '';

    for(let char of s){
        if(!isNaN(char)){
            num = num * 10 + Number(char);
        }else if(char === '['){
            strStack.push(res);
            res = '';
            numStack.push(num);
            num = 0;
        }else if(char ===']'){
            res = strStack.pop() + res.repeat(numStack.pop());
        }else{
            res += char;
        }
    }
    return res;

};

复杂度分析

• 时间复杂度：O(N)，其中 N 为数组长度。
• 空间复杂度：O(1)

[XingZhaoDev]

思路: Stack 代码：

func decodeString(_ s: String) -> String {
    var stack = [String]()

    for char in s {
        if char != "]" {
            stack.append(String(char))
        } else {
            var decoded = ""

            while stack.last! != "[" {
                decoded = stack.popLast()! + decoded
            }
            stack.popLast()

            var k = 0
            var offset = 1
            while !stack.isEmpty, let digit = Int(stack.last!) {
                stack.popLast()
                k += offset * digit
                offset *= 10
            }

            stack.append(String(repeating: decoded, count: k))
        }
    }

    return stack.joined()
}

复杂度: Time: O(K N), Space: O(K N) where K is the product of all "k"s and N is the number of encoded characters

[youzhaing]

题目：394. 字符串解码

思路：

利用栈先进后出的特性模拟括号。遍历字符串，判断每个字符类型并进行不同处理。栈主要用来纪律记录每次括号之前已经整理好的字符串以及括号中字符串的循环次数。

python代码

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res, tmp, mul = '', '', 0
        for i in s:
            if i.isdigit(): 
                mul = int(i) + 10 * mul
            elif i == '[': 
                stack.append((mul, res))
                res, mul = '', 0
            elif i == ']':
                mul1, tmp = stack.pop()  # tmp为[之前的所有字符
                res = tmp + mul1 * res
            else:
                res += i
        return res

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n), e.g. '1[a1[a1[a]]]'

[zhongranHerz]

解法一：辅助栈法 本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

算法流程：

构建辅助栈 stack， 遍历字符串 s 中每个字符 c； 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算； 当 c 为字母时，在 res 尾部添加 c； 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 0： 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作； 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...] 字符串。 进入到新 [ 后，res 和 multi 重新记录。 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中: last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 a； cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 "3[a2[c]]" 中的 2。 返回字符串 res。

复杂度分析：

时间复杂度 O(N)，一次遍历 s； 空间复杂度 O(N)，辅助栈在极端情况下需要线性空间，例如 2[2[2[a]]]。

# k神写法
class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            elif c == ']':
                cur_multi, last_res = stack.pop()
                res = last_res + cur_multi * res
            elif '0' <= c <= '9': # 这里用isdigit（）合适
                multi = multi * 10 + int(c)            
            else:
                res += c
        return res

# 自己的
class Solution:
    def decodeString(self, s: str) -> str:
        stack = []  # (str, int) 记录之前的字符串和括号外的上一个数字
        num = 0
        res = ""  # 实时记录当前可以提取出来的字符串
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == "[":
                stack.append((res, num))
                res, num = "", 0
            elif c == "]":
                top = stack.pop()
                res = top[0] + res * top[1]
            else:
                res += c
        return res

[ceramickitten]

思路

对s中的字符进行压栈, 如果遇到']'说明遇到了一个最内层的表达式, 进行解析, 再压到栈里.

代码

class Solution:
    def decodeString(self, s: str) -> str:
        # space: O(N)
        stack = []
        # time : O(N)
        for c in s:
            if c == ']':
                token = ''
                while stack and stack[-1] != '[':
                    token = stack.pop() + token
                stack.pop()
                k = ''
                while stack and stack[-1].isnumeric():
                    k = stack.pop() + k
                stack.append(token * int(k))
            else:
                stack.append(c)
        return ''.join(stack)

复杂度分析

N为s.length

• time: O(N)
• space: O(N)

[nikojxie]

思路

1.创建两个栈，一个存数字，一个存字符 2.遇到 '[' 时，把数字和当前的结果分别放入两个栈内 3.遇到 ']' 时，把当前的结果 (数字栈顶的数字）次，再加上字符栈顶的字符，视作当前的结果 4.遇到数字时，multi值记录，可能会有几位数，所以 10 5.遇到普通字符时，直接在当前结果后面加上该字符

代码

function decodeString (s) {
  let multiStack = [], resStack = [], res = '', multi = 0
  for(let str of s) {
    if(str === '[') {
      multiStack.push(multi)
      resStack.push(res)
      multi = 0
      res = ''
    } else if(str === ']') {
      res = resStack.pop() + res.repeat(multiStack.pop())
    } else if(!isNaN(str)) {
      multi = multi*10 + parseInt(str)
    } else {
      res += str
    }
  }
  return res
}

复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[2learnsomething]

思路

栈的使用，与判断括号匹配相似

代码

class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            elif c == ']':
                cur, last = stack.pop()
                res = last + cur * res
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)            
            else:
                res += c
        return res

复杂度

时间复杂度:O(N)

空间复杂度:O(N)

[herbertpan]

Algo

// 11:18PM // Constraints: // 1. K > 0 // 2. 2[4]/3a/2[] // 3. digits are only repeat

// test case: // 1. abc // 2. a3[a] // 3. 3[a3[b]]c

// "a3[a2[c]]"
// 1. get the string => a // 2. get the repeated number => 3 // 3. get the repeated string => a2[c] // 3.1 get the string => a // 3.2 get the repeated number => 2 // 3.3 get the repeated string => c // 3.3.1 get the string => c // 3.3.2 get the repeated number => 0 // 3.4 get built string repeated number returned string => 2 c = cc // 3.5 prefix string => a + cc = acc // 4. get built string repeated number returned string => 2 acc = accaccacc // 5. prefix string => a + accaccacc = aaccaccacc

// "3[2[c]]"
// 1. get string => ""
// 2. get the repeated number => 3
// 3. get the repeated string => 2[c]
//     3.1 get the string => ""
//     3.2 get the repeated number => 2
//     3.3 get the repeated string => c
//         3.3.1 get the string => c
//         3.3.2 get repeated number => 0  ==> !end!
//     3.4 get built string repeated number * returned string => 2 * c = cc
//     3.5 prefix string => "" + cc = cc
// 4. get built string repeated number * returned string => 3 * cc = cccccc
// 5. prefix string => "" + cccccc = cccccc

Code

class Solution { public String decodeString(String s) {
return helper(s, 0, s.length() - 1); }

private String helper(String s, int startIndex, int endIndex) {     //         "3[a]2[bc]"       // a
    int index = startIndex;                                         // index = 0 
    StringBuilder ans = new StringBuilder();
    while (index <= endIndex) {
        String prefixString = getPrefixString(s, index, endIndex);      // prefix= ""
        index += prefixString.length();                                 // index = 0;

        String repeatedNumber = getRepeatedNumber(s, index, endIndex);  // repeat =  "3"
        if (repeatedNumber.length() == 0 || Integer.valueOf(repeatedNumber) == 0) {
            ans.append(prefixString);
            continue;
        }
        index += repeatedNumber.length();                                // index = 1

        index += 1; // forward one step to skil [                        // index = 2; 
        int repeatedStringEnds = getRepeatEndIndex(s, index, endIndex);  // reapted = 3
                                                                         // rewind 1 step for ]
        String repeatedString = helper(s, index, repeatedStringEnds - 1); // str = "a"
        index = repeatedStringEnds + 1;
        String returnString = "";

        int repeatedNum = Integer.valueOf(repeatedNumber);                // return = "aaa"
        for (int i = 0; i < repeatedNum; i++) {
            returnString += repeatedString;
        }
        ans.append(prefixString).append(returnString);
    }

    return ans.toString();                       //
}
                                                                          // |
private String getPrefixString(String s, int startIndex, int endIndex) {  // 3[a]2[bc]
    // keep tracking until meets a number or ends
    StringBuilder sb = new StringBuilder();
    int index = startIndex;
    while (index <= endIndex && s.charAt(index) >= 'a' && s.charAt(index) <= 'z') {
        sb.append(s.charAt(index));
        index++;
    }
    return sb.toString();
}
                                                                                       // ||
private String getRepeatedNumber(String s, int startIndex, int endIndex) {             // 3[a]2[bc]
    // get first start should be a number or the end 
    StringBuilder sb = new StringBuilder();
    int index = startIndex;                                                            // sb = 3
    while (index <= endIndex && s.charAt(index) >= '0' && s.charAt(index) <= '9') {
        sb.append(s.charAt(index));
        index++;
    }
    return sb.toString();
}                                                                              
                                                                             //   ||
private int getRepeatEndIndex(String s, int startIndex, int endIndex) {      // 3[a]2[bc]
    // get first start should be a [ or end index                            //.012345678
    int numberOfBackBracket = 0;                                             //    1
    int index = startIndex;
    while (index <= endIndex) {                                              //    
       if (s.charAt(index) == ']') {
           numberOfBackBracket++;
       }

       if (numberOfBackBracket == 1) {
           return index;
       }

       if (s.charAt(index) == '[') {
           numberOfBackBracket--;
       }
        index++;
    }

    return -1;
} 

}

Complexity

1. Time: O(n);
2. Space: O(n)

[ccslience]

/*

• 1、思路: 利用栈，非']'即入栈，否则出栈;
• 2、出栈的时候注意将一个[]之内解码好的压回栈，最后在对栈中所有解码后的字符串进行拼接;
• 2、需要注意char转string，利用string的构造函数string(n, char);
• 3、数字可能是多位的，因此需要注意转换;
• 4、时间复杂度O(n), 空间复杂度O(n)
• */

string decodeString(string &s)
    {
        stack<string> data;
        for(int i = 0; i < s.length(); i++)
        {
            // 数字、字母和左方括号入栈
            if ((s[i] >= '0' && s[i] <= '9') || (s[i] == '[') || (s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
            {
                data.push(string(1, s[i]));
            }
                // 右方括号出栈
            else
            {
                string cur = "";
                while(data.top().data()[0] != '[')
                {
                    cur = data.top() + cur;
                    data.pop();
                }
                data.pop();
                // 取整数
                int digit = 0;
                int carry = 1;
                while(!data.empty() && data.top().data()[0] >= '0' && data.top().data()[0] <= '9')
                {
                    digit = digit + (data.top().data()[0] - '0') * carry;
                    carry *= 10;
                    data.pop();
                }
                string res = "";
                for (int j = 0; j < digit; j++)
                    res += cur;
                data.push(res);
            }
        }
        string res = "";
        while(!data.empty())
        {
            res = data.top() + res;
            data.pop();
        }
        return res;
    }

[fenchuiyun]

思路

把经过编码的字符串，还原成解码后的字符串 需要解析匹配口号，如[]，可以利用栈

class Solution {
    public String decodeString(String s) {
        //  把经过编码的字符串，还原成解码后的字符串   k[encoded_string]
        // 我们需要解析匹配括号,如[] ，想到利用栈
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        int idx = 0;
        while (true){
            if (idx>=chars.length){
                break;
            }
            char val = chars[idx];
            if (val==']'){
                String blabla = getString(stack);
                for (char c : blabla.toCharArray()) {
                    stack.push(c);
                }
            }else{
                stack.push(val);
            }
            idx++;
        }
        String reversedResult = "";
        while (!stack.isEmpty()){
            Character pop = stack.pop();
            reversedResult += pop;
        }

        return new StringBuilder(reversedResult).reverse().toString();
    }

    private String getString(Stack<Character> stack) {
        if (stack.isEmpty()){
            return "";
        }
        String reversedVal = "";
        while (true){
            Character pop = stack.pop();
            if (pop=='['){
                break;
            }else {
                reversedVal += pop;
            }
        }
        StringBuilder sb = new StringBuilder(reversedVal);
        String value = sb.reverse().toString();
        String reverseCount = "";
        while (!stack.isEmpty()){
            Character countNumb = stack.peek();
            if (countNumb-'9'>0){
                break;
            }
            reverseCount+=countNumb;
            stack.pop();
        }
        Integer count = Integer.valueOf(new StringBuilder(reverseCount).reverse().toString());
        String result = "";
        for (Integer i = 0; i < count; i++) {
            result+=value;
        }
        return result;
    }
}

复杂度

时间复杂度：O(n)
空间复杂度: O(n)

[zch-bit]

Day 4

func decodeString(s string) string {
    str, _ := expand([]byte(s), 0)
    return string(str)
}

func expand(s []byte, i int) ([]byte, int) {
    var expanded []byte
    var digits []byte
    for i < len(s) && s[i] != ']' {
        c := s[i]
        if c >= 'a' && c <= 'z' {
            expanded = append(expanded, c)
        } else if c >= '0' && c <= '9' {
            digits = append(digits, c)
        } else if c == '[' {
            nested, idx := expand(s, i+1)
            numTimes, _ := strconv.Atoi(string(digits))
            digits = digits[:0]
            for numTimes > 0 {
                expanded = append(expanded, nested...)
                numTimes--
            }
            i = idx
        }
        i++
    }
    return expanded, i
}

Complexity: Time: O(n), Space: O(n)