【Day 4 】2021-09-13 - 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"

[ImSingee]

简单粗暴利用栈完成

impl Solution {
    pub fn decode_string(s: String) -> String {
        let mut result = "".to_string();
        let mut numbers: Vec<usize> = Vec::new();
        let mut letters: Vec<String> = Vec::new();

        let mut i = 0;
        while i < s.len() {
            let c = s.bytes().nth(i).unwrap() as char;

            if c.is_ascii_alphabetic() {
                let s = Solution::scan_letter(&s, &mut i);

                if let Some(last) = letters.last_mut() {
                    *last += &s;
                } else {
                    result += &s;
                }

                continue;
            }

            if c.is_ascii_digit() {
                let n = Solution::scan_number(&s, &mut i);
                numbers.push(n);
                continue;
            }

            if c == '[' {
                letters.push("".to_string());
                i += 1;
                continue;
            }

            if c == ']' {
                let part = letters.pop().unwrap().repeat(numbers.pop().unwrap());

                if let Some(last) = letters.last_mut() {
                    *last += &part;
                } else {
                    result += &part;
                }

                i += 1;
                continue;
            }

            panic!("unknown char {}", c);
        }

        result
    }

    fn scan_letter(s: &str, i: &mut usize) -> String {
        let mut result = "".to_string();

        while *i < s.len() {
            let c = s.bytes().nth(*i).unwrap() as char;

            if c.is_ascii_alphabetic() {
                result.push(c);
                *i += 1;
            } else {
                break;
            }
        }

        result
    }

    fn scan_number(s: &str, i: &mut usize) -> usize {
        let mut result = 0;

        while *i < s.len() {
            let c = s.bytes().nth(*i).unwrap() as char;

            if let Some(n) = c.to_digit(10) {
                result = 10 * result + (n as usize);
                *i += 1;
            } else {
                break;
            }
        }

        result
    }
}

[Bochengwan]

思路

利用两个栈，一个存数字，一个存字符，每次遇到括号进行处理。

代码

class Solution:
    def decodeString(self, s: str) -> str:
        bracket_stack = []
        number_stack = []
        c = ''
        n = ''
        for e in s:

            if e.isdigit():
                n+=e
            elif e == '[':
                bracket_stack.append(c)
                number_stack.append(n)
                n = ''
                c = ''
            elif e == ']':

                c = (bracket_stack.pop() + c*int(number_stack.pop()))
            else:
                c += e
        return c

复杂度分析

• 时间复杂度：O(N)，其中 N 为字符串长度。
• 空间复杂度：O(m+n), m = len(number_stack), n = len(bracket_stack）

[Davont]

思路

利用栈,以前做过，还是对中括号的匹配，很经典一题

代码

 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    const numStack = [];
    const strStack = [];
    let repeatTimes = '';
    for (let i = 0; i< s.length; i++) {
      const char = s[i];
      if(!Number.isNaN(+char)){
          repeatTimes += char;
          continue;
      }
      if(repeatTimes){
        numStack.push(+repeatTimes);
        repeatTimes = '';
      }
      if(char === ']'){
          let repeatStr = '';
          while(strStack.length && strStack.slice(-1)[0]!=='['){
            let a = strStack.slice(-1);
            repeatStr = strStack.pop() + repeatStr;
          }
          strStack.pop();
          strStack.push(repeatStr.repeat(numStack.slice(-1)));
          numStack.pop();
      }else{
          strStack.push(char);
      }
    }
    return strStack.join('');
};

[yanglr]

思路

规律: 对于每一个小段, 如果有n层配对的中括号, 那么它的格式是: n[xxx]

如果出现次数是1, 那么它的格式是: xxx, 1和[]直接不写, 和原串相同.

如果存在多层中括号, 则需要使用栈或递归的方式解决。

栈

使用两个stack (后面直接将deque用作stack, 性能更好), 一个stack存放重复出现的次数(也就是字符串[xxx]前紧挨着的数字)。 另一个stack存储扫描到的字符串。 将结果字符串记作resStr。

代码

实现语言: C++

class Solution {
public:
    string decodeString(string s) {
        deque<int> numStack;
        deque<string> strStack;
        string resStr;

        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            char ch = s[i];
            if (isdigit(ch))
            {
                int digit = ch - '0';
                while (i < n - 1 && isdigit(s[i + 1]))
                {
                    digit = digit * 10 + s[i + 1] - '0';
                    i++;
                }
                numStack.push_front(digit);
            }
            else if (ch == '[')
            {
                strStack.push_front(resStr);
                resStr.clear();
            }
            else if (ch == ']')
            {
                string tmp = strStack.front();
                strStack.pop_front();
                int repeatCount = numStack.front();
                numStack.pop_front();
                for (int j = 0; j < repeatCount; j++)
                    tmp.append(resStr);

                resStr = tmp;
            }
            else resStr.push_back(ch);  // 直接取出来放进结果字符串中
        }
        return resStr;
    }
};

代码已上传到: leetcode-ac/91algo daily - github.com

复杂度分析

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

[cicihou]

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

时间：最坏情况 O(n^2) 空间：O(n)

[chenming-cao]

解题思路

用栈来解决。重复的部分满足格式k[encoded_string]，先将除]外的字符入栈，遇到]说明重复的部分出现，先出栈字母，再出栈[，最后出栈数字。根据数字将重复部分重新入栈。最后出栈所有字符获得字符串即为结果。

代码

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

        for (char c: s.toCharArray()) {
            if (c != ']') {
                stack.push(c); // push characters into stack if it is not ']'
            }
            else {
                StringBuilder sb = new StringBuilder();
        // get the repeated characters
                while (!stack.isEmpty() && Character.isLetter(stack.peek())) {
                    sb.insert(0, stack.pop());
                }

                String sub = sb.toString();
        // pop '[' from stack
                stack.pop();

                sb = new StringBuilder();
        // get the repeated times
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    sb.insert(0, stack.pop());
                }

                int count = Integer.parseInt(sb.toString());
        // push the repeated characters back into stack
                while (count > 0) {
                    for (char element: sub.toCharArray()) {
                        stack.push(element);
                    }
                    count--;
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
        }

        return res.toString();
    }
}

复杂度分析

令字符串长度为n

• 时间复杂度：O(n)，需要遍历字符串
• 空间复杂度：O(n)，创建栈储存字符

[yachtcoder]

Use a stack to process every pair of brackets. Tokenization is a bit hacky. Processing each char might be more concise. Time: O(n^2) because even though each char is processed once, manipulating the string is O(n) each time. Space: O(n)

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        toks = []
        s = list(s)
        for i in range(1, len(s)):
            prev = s[i-1]
            if prev[-1].isalpha() != s[i][0].isalpha():
                s[i]= " "+s[i]
        s = ''.join(s).replace("[", " [ ").replace("]", " ] ")
        for t in s.split():
            if t == "]":
                st = ""
                n = 0
                while stack:
                    c = stack.pop()
                    if c == "[": break
                    st = c+st
                n = int(stack.pop())
                stack.append(st*n)
            else:
                stack.append(t)
        return ''.join(stack)

[xieyj17]

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        curr_num = 0
        curr_string = ''
        for c in s:
            if c == '[':
                stack.append(curr_string)
                stack.append(curr_num)
                curr_string = ''
                curr_num = 0
            elif c == ']':
                num = stack.pop()
                prev_string = stack.pop()
                curr_string = prev_string + num*curr_string
            elif c.isdigit():
                curr_num = curr_num*10 + int(c)
            else:
                curr_string += c
        return curr_string

看了半天还是不会做，然后看了leetcode 的答案模仿着写了一遍，大概有点懂了

[biancaone]

思路

用栈来记录number和之前的字符串。遇到左括号，就压栈，遇到右括号，弹栈，并更新当前的字符串。

---

代码

class Solution:
    def decodeString(self, s: str) -> str:
        if not s:
            return ''

        stack = []

        cur_string = ''
        cur_num = 0

        for char in s:
            if char == '[':
                stack.append(cur_string)
                stack.append(cur_num)
                cur_string = ''
                cur_num = 0
            elif char == ']':
                prev_num = stack.pop()
                prev_string = stack.pop()
                cur_string = prev_string + cur_string * prev_num
            elif char.isdigit():
                cur_num = cur_num * 10 + int(char)
            else:
                cur_string += char

        return cur_string

---

复杂度

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

  ---

[JiangyanLiNEU]

Idea

I use stack to solve this problem. The main idea is:

• an array called left to store all the elements we saw//processed
• when we see a number element, we check if this digit belong to a greater number (for examplt, if we got '0' and the last element in left is '3', so obviously, we make it to '30'), if so, we add this one to the previous on in left array, otherwise we append this number into left array
• when we see [ elements, we record its index in an array called firstpart.
• when we see ] elements, we need to find its match [ part in firstpart array. then we know, the number is right before the [ elements and the segments needed to be repeated is after [ elements. Then we process this segment and append it to the left array. In the meantime, we need to update the index, so we can keep track of the location of [.

Implement ( Runtime=O(n), space=(n))

class Solution(object):
    def decodeString(self, s):
        def process(time, array):
            seg = ''.join(array)
            return seg*time

        result = ''

        firstpart = []
        left = []
        index = -1
        while s:
            cur = s[0]
            s = s[1:]

            if left and left[-1].isnumeric() and cur.isnumeric():
                left[-1] += cur
            else:
                left.append(cur)
                index += 1
                if cur == '[':
                    firstpart.append(index)
                elif cur == ']':
                    match = firstpart.pop()
                    time = int(left[match-1])
                    seg = left[match+1:index]
                    index = match-2+1
                    left = left[:match-1]
                    left.append(process(time, seg))
        return ''.join(left)

[nonevsnull]

思路

stack, string

这题的主要考点

• 利用栈，在遇到右括号]时pop进行运算，运算完成后push回到stack；
  • 这个技巧可以说用的蛮多，类似的技巧在1381也用到过；
  • 字符 * 数字 = 新字符；这里字符和数字可以分别存在两个栈，也可以存在一个栈，判断条件不同；

需要注意的地方

• 因为用的是栈，所以每次pop之后，得到的String顺序是反的，数字也是反的，得reverse；
• 注意每次数字部分都需要reverse再做repeat操作；但字符只需要最后对res做reverse操作，如果在循环体就对字符做reverse，比较容易混淆；
• String操作，要避免str = str + "abc"或str = "abc" + str这类操作，因为它们是O(N)的；虽然每次操作的N不是很大，但最坏的情况可以和s.length()一样，最终导致O(N^2);
• 用StringBuilder.append来做，是O(1)的。而且可以很方便的使用reverse()方法。

代码

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

        for(int i = 0;i < s.length();i++){
            if(s.charAt(i) == ']'){
                //get chars inside []
                StringBuilder s_sb = new StringBuilder();
                while(!stack.isEmpty() && !stack.peek().equals("[")){
                    s_sb.append(stack.pop());
                }
                stack.pop();//for '['

                //get numeric multiplier
                StringBuilder n_sb = new StringBuilder();
                while(!stack.isEmpty() && stack.peek().charAt(0) <= '9' && stack.peek().charAt(0) >= '0'){
                    n_sb.append(stack.pop());
                }

                stack.add(s_sb.toString().repeat(Integer.valueOf(n_sb.reverse().toString())));
            } else {
                stack.add(String.valueOf(s.charAt(i)));
            }
        }

        StringBuilder resb = new StringBuilder();
        while(!stack.isEmpty()){
            resb.append(stack.pop());
        }
        return resb.reverse().toString();
    }
}

复杂度

O(N)，循环体会从头到尾遍历s.length(); O(N)，要维护一个栈；

[zhangzz2015]

思路

• 括号匹配问题，使用递归或者栈的办法，和处理计算器的括号处理类似，使用递归办法，递归需要输入，start的位置，对应[后面的位置，输出需要两个内容，1个对应[]内的字符串，另外也需要传出，当前结束的位置，所以采用引用办法返回start，递归完成，后面继续处理下一个。碰到[ 进入递归，碰到 ]返回string，另外要注意num 清零。 C++ Code:

class Solution {
public:
    string decodeString(string s) {

        int start =0; 
        return helper(s, start); 
    }

    string helper(string& s, int& start)
    {
        int num =0; 
        string ret;
        for(; start < s.size(); start++)
        {
            if(s[start]-'0'>=0 && s[start]-'0'<=9) // is digital
            {
                num = num*10 + (s[start] - '0' );
            }
            else if(s[start]=='[')
            {
                start++;  
                string oneWord = helper(s, start);
                for(int i=0; i< num; i++)
                {
                    ret +=oneWord; 
                }
                num =0;                 
            }
            else if(s[start] == ']')
            {
                return ret;
            }
            else // charater. 
            {
                ret.push_back(s[start]); 
            }

        }  
        return ret;

    }
};

[ruohai0925]

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

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':  # 处理>10的数字
                multi = multi * 10 + int(c)
            else:
                res += c
        return res

复杂度分析

O(N)，循环体会从头到尾遍历s.length(); O(N)，要维护一个栈；

[comst007]

394. 字符串解码

思路

借助数据结构 中的 栈。一个栈用来存储中间计算结果st1，一个栈用来存储出现次数 st2。 从头开始扫描：

• 遇到连续是数字的字符把它转化成最终的整数存入到st2中。
• 遇到的字符是大小写字母或者[就把它存储到st1 中。
  • 遇到的字符是]， 则逐渐弹出st1中的字符，直到[。弹出的字符形成的字符串记为s_tmp，然后从st2中弹出一个整数s_feq，最后将s_tmp重复s_feq次，然后把结果存入st1中。

最后返回st1中的字符构成的字符串。

---

代码

• C++

class Solution {
public:
    string decodeString(string s) {
        vector<int> num_st;
        vector<char> ch_st;
        for(int ii = 0, cur_cnt = 0; ii < s.size(); ++ ii){
            if(s[ii] <= '9' && s[ii] >= '0'){
                cur_cnt = cur_cnt * 10 + s[ii] - '0';
                continue;
            }
            if(cur_cnt > 0){
                 num_st.push_back(cur_cnt);
                 cur_cnt = 0;
            }

            if( (s[ii] <= 'z' && s[ii] >= 'a') || (s[ii] <= 'Z' && s[ii] >= 'A') || (s[ii] == '[')){
                ch_st.push_back(s[ii]);
                continue;
            }
            if(s[ii] == ']'){
                vector<char> tmp_ch;
                while(ch_st.back() != '['){
                    tmp_ch.push_back(ch_st.back());
                    ch_st.pop_back();
                }
                ch_st.pop_back();
                int feq = num_st.back();
                num_st.pop_back();
                while(feq --){
                    for(int jj = tmp_ch.size() - 1; jj >= 0; -- jj){
                        ch_st.push_back(tmp_ch[jj]);
                    }
                }
            }
        }

        return string(ch_st.begin(), ch_st.end());
    }

};

---

复杂度分析 假设最终的解码后的字符串长度为m

• 时间复杂度 遍历一遍字符串的字符 O(m)
• 空间复杂度 需要借助栈来辅助计算 O(m)

[zhangzz2015]

思路

• 考虑使用栈的办法，记录num ，以及[]内部的string，num栈和string栈是一一匹配的。碰到[ 。我们就入栈，碰到]，我们就出栈。并把出栈的字符串复制num次，唯一要注意的是，如果出栈后，栈里还有元素，我们需要把当前复制后的元素再追加到栈顶的字符串，为下一次做准备，如果栈顶没有元素，则可直接push 到要返回的字符串中。时间复杂度为，遍历字符串为O(N) 如果有[ ] 则需要多增加字符串copy。空间复杂度为O(N)。

C++ Code:

class Solution {
public:
    string decodeString(string s) {

        // use stack. 
        vector<int> numStack; 
        vector<string> numString;
        string ret; 
        int num =0; 
        for(int i=0; i< s.size(); i++)
        {
            if(s[i]-'0'>=0 &&s[i]-'0'<=9) // is number
            {
                num = num*10+(s[i]-'0');
            }
            else if(s[i]=='[')
            {
                numStack.push_back(num);
                string tmp; 
                numString.push_back(tmp);
                num=0;                
            }
            else if(s[i]==']')
            {
                int numVal = numStack.back();
                string oneWord = numString.back(); 
                numString.pop_back();
                if(numString.size())
                {
                    for(int i=0; i< numVal; i++)
                    {
                        numString.back() +=oneWord;
                    }   
                }
                else
                {
                     for(int i=0; i< numVal; i++)
                    {
                        ret +=oneWord;
                    }                   
                }
                numStack.pop_back();

            }
            else
            {
              if(numString.size())  
                numString[numString.size()-1].push_back(s[i]);
              else
                ret.push_back(s[i]);   
            }
        }
        return ret;   
    }
};

[leungogogo]

LC394. Decode String

Method 1. Recursion

Main Idea

First, I think we can use recursion to handle nested cases like 3[a2[bc]], where we can decode 2[bc] first, and we get 3[abcbc], which is the same problem with different size.

Algorithm

We need a global variable index to indicate which index are we currently processing.

• Base case: if there are no brackets, we just return the string itself.
• When we see a digit, we convert it to number cnt, increment index to skip the [, and pass the string to recursive call.
• When we see a ], we can return from this recursive call.

Code

class Solution {
    private int index = 0;
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        while (index < n && s.charAt(index) != ']') {
            char c = s.charAt(index);
            if (Character.isDigit(c)) {
                int cnt = 0;
                while (Character.isDigit(s.charAt(index))) {
                    cnt = cnt * 10 + s.charAt(index) - '0';
                    ++index;
                }
                ++index;
                String str = decodeString(s);
                for (int i = 0; i < cnt; ++i) {
                    sb.append(str);
                }
            } else {
                sb.append(c);
            }
            ++index;
        }
        return sb.toString();
    }
}

Complexity Analysis

Time: O(S), where S is the length of the decoded string.

Space: O(s), where s is the length of the input string, as the space complexity depends on the depth of recursive calls, and we can have at most s nested brackets.

Method 2. Stack

Main Idea

We can also use stack to solve problems of parentheses matching, in this problem, we will push everything to the stack until we see a ], then we pop things from the stack until we found its matching [. And we can decode the string, and push the decoded string back to the stack.

Code

class Solution {
    public String decodeString(String s) {
        int n = s.length();
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            if (c != ']') {
                stack.push(c);
            } else {
                List<Character> list = new ArrayList<>();
                while (stack.peek() != '[') {
                    list.add(stack.pop());
                }
                stack.pop();

                int cnt = 0, base = 1;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    int digit = stack.pop() - '0';
                    cnt += (digit * base);
                    base *= 10;
                }

                for (int l = 0; l < cnt; ++l) {
                    for (int j = list.size() - 1; j >= 0; --j) {
                        stack.push(list.get(j));
                    }
                }

            }
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        sb.reverse();
        return sb.toString();
    }
}

Complexity Analysis

Time: O(S), where S is the length of the decoded string.

Space: O(S), since we use a stack to store all the characters.

[Menglin-l]

思路：

因为方括号可能内嵌，需从最内层decode，可使用一个辅助栈：

1. 将字符依次入栈，遇到第一个']'时出栈，至第一个'['前的数字截止.

2. 根据数字解码得到相应的字符串。

3. 将完成解码后的字符串重新入栈。

4. 重复1-3中操作。

---

代码部分：

class Solution {
    public String decodeString(String s) {

        if (s == null || s.length() == 0) {
            return "";
        }

        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c != ']') {
                stack.push(c);
                // 遇到']'
            } else {
                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty() && Character.isLetter(stack.peek())) sb.insert(0, stack.pop());

                String str = sb.toString();
                stack.pop(); // 弹出匹配的'['

                sb = new StringBuilder();
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) sb.insert(0, stack.pop());

                int cnt = Integer.valueOf(sb.toString());

                // 根据数字解码得到相应的字符串
                while (cnt > 0) {
                    for (char cc : str.toCharArray()) stack.push(cc);

                    cnt --;
                }
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) res.insert(0, stack.pop());

        return res.toString();
    }
}

---

复杂度：

Time: O(n^2)

Space: O(n)

[MonkofEast]

394. Decode String

Click Me

Algo

1. Consider innermost decoding, stack is good
2. new a stack for final output
3. new a list for temp saving decode
4. travel through the original str
5. if not ']', continue
6. if ']', stop, decode

Code

class Solution:
    def decodeString(self, s: str) -> str:
        # the key here is to consider cases like jksd19[dsl]fion3[acc2[d]]
        # this nested pattern should be decode from innermost str
        # so stack is good for this task
        # KEY!!!: ']' on the top of stack is the starting point to decode

        stack = []
        decodeList = []

        # travel the ori str
        for i in range(len(s)):
            # if not , travel
            if s[i] != ']':
                stack.append(s[i])
            # if ']', stop, start decoding
            else:
                while stack[-1] != '[': decodeList.insert(0, stack.pop())
                stack.pop() # delete '['
                # find the multi times
                times, multi = 0, 1
                while stack and stack[-1].isnumeric():
                    times += multi*int(stack.pop())
                    multi *= 10
                stack = stack + decodeList*times
                decodeList.clear()

        # (str).join(list): return a str
        return "".join(stack)

Comp

T: O(N)

S: O(max(decoded-list))

[HackBL]

• Stack判断括号

  class Solution {
  public String decodeString(String s) {
      Deque<StringBuilder> strStack = new LinkedList<>();
      Deque<Integer> intStack = new LinkedList<>();
      StringBuilder sb = new StringBuilder();
      int k = 0;
  
      for (char c: s.toCharArray()) {
          if (Character.isDigit(c)) {
              k = k * 10 + (c - '0');
          } else if (c == '[') {
              strStack.push(sb);
              intStack.push(k);
  
              sb = new StringBuilder();
              k = 0;
          } else if (c == ']') {
              StringBuilder tmp = sb;
              sb = strStack.pop();
  
              for (int i = intStack.pop(); i > 0; i--)
                  sb.append(tmp);
          } else {
              sb.append(c);
          }
      }
  
      return sb.toString();
  }
  }

• Time: O(maxK*n) such as k[string]
• Space: O(n)

[littlemoon-zh]

day 4

Leetcode 394 Decode String

这题还是有些难度的，用到了stack，其实也是一种递归的思维，因为递归就是栈。然后再根据题目要求，写出满足的逻辑即可。

由于题目说明了，所有的格式都是规范的，不会出现3a这种情况，所以我们只要按照规则做就行了。

• 遇到数字时，将其压入数字栈中；
• 遇到[和其他字母时，压入符号栈中；
• 遇到]时，表示我们可以进行一个字符串拼接了；
  • 拼接的字符串来自符号栈中，不断出栈，直到遇到第一个[，表示当前的字符串完毕；
  • 接着从数字栈中弹出一个元素，表示将刚才的字符串重复若干遍；
  • 再将重复过的字符串压入符号栈中，继续上述过程；

最后符号栈中的各个字符串都是并列的关系，比如4[a]3[cd]，最终的结果是 ['aaaa', 'cdcdcd']，使用join函数将它们拼接到一起就可以了。

代码如下：

class Solution:
    def decodeString(self, s: str) -> str:
        i = 0
        num = []
        ch = []

        while i < len(s):
            if s[i].isdigit():
                n = 0
                while s[i].isdigit():
                    n = n * 10 + int(s[i])
                    i += 1
                num.append(n)
            elif s[i] == ']':
                ss = []
                while ch[-1] != '[':
                    ss.insert(0, ch.pop(-1))
                ch.pop(-1)
                ch.append(''.join(ss) * num.pop(-1))
                i += 1
            else:
                ch.append(s[i])
                i += 1

        # print(ch)
        return ''.join(ch)

[wangzehan123]

代码

• 语言支持：Java

Java Code:

class Solution {
    int index = 0;
    public String decodeString(String s) {
        // write your code here
        if (s.length() == 0) {
            return "";
        }

        StringBuilder sb = new StringBuilder();

        int repeat = 0;

        while (index < s.length()) {
            char c = s.charAt(index);
            if (c == '[') {
                index++;
                String sub = decodeString(s);
                for (int i = 0; i < repeat; i++) {
                    sb.append(sub);
                }
                repeat = 0;
                index++;
            } else if (c == ']') {
                return sb.toString();
            } else if (Character.isDigit(c)) {
                repeat = repeat * 10 + c - '0';
                index++;
            } else {
                sb.append(c);
                index++;
            }
        }

        return sb.toString();
    }
}

复杂度分析

令 n 为数组长度。

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

[pophy]

思路

• 利用两个stack，stringStack / counterStack
• 遍历表达式 当前字符记为c， index i
  • 如果 c 是数字
  • c 的下一位也是数字， 则一直向后拓展到 j, subString(i,j)转为数字 压入counterStack
  • 如果c == '[' 表示 subString开始，向stringStack中压入空串 “”
  • 如果是c == ']' 表示sub string结束
  • counterStack弹出counter数值
  • stringStack弹出当前substring
  • 循环counter次substring, 压回stringStack
  • 非[ / ] 表示当前字符为substing中的一个 stringStack .push(stringStack.pop() + c)
• 最后stringStack中的string就是答案

Java code

    public String decodeString(String s) {
        Stack<String> stringStack = new Stack();
        Stack<Integer> counterStack = new Stack();
        stringStack.push("");
        //starting index
        int i = 0;
        while (i < s.length()) {
            Character c = s.charAt(i);
            //match number
            if (c >= '0' && c <= '9') {
                int j = i + 1;
                while (s.charAt(j) >= '0' && s.charAt(j) <= '9') {
                    j++;
                }
                counterStack.push(Integer.parseInt(s.substring(i, j)));
                i = j;
            } else {
                //match string
                if (c == '[') {
                    stringStack.push("");
                } else if (c == ']') {
                    int counter = counterStack.pop();
                    StringBuilder sb = new StringBuilder();
                    String subString = stringStack.pop();
                    for (int k = 0; k < counter; k++) {
                        sb.append(subString);
                    }
                    stringStack.push(stringStack.pop() + sb);
                } else {
                    stringStack.push(stringStack.pop() + c);
                }
                i++;
            }
        }
        return stringStack.pop();
    }

时间复杂度 & 空间复杂度

• 时间
  • O(n)
• 空间
  • O(n)

[a244629128]

思路

假如给的string是 "abc10[cd]xyz"

stack 用来暂时保存 prevString 和 currNum

currString保存字母

currNum保存数字

有四种情况

1.当前char是字母： 直接加到currString里面

​ 2.当前char是数字： 直接加到currNum里面，（line 20） 还有一个 currNum10 是为了应对如果数字是more than 1 digit 的情况。 例如 "10[cd]" 这个string需要10个‘cd’重复 ，如果没有currNum 10， currNum 遇到第一个数字的时候会加一 currNum=1，遇到第二个数字0会加零 currNum+0= 1+0=1，得到的数字并不正确。 如果加上currNum10 ，currNum 遇到第一个数字的时候会加一 currNum=1，遇到第二个数字0会把currNum先乘以10 再加零， currNum10+0= 1x10+0=10;

3.当前char 是 '[' ： 如果遇到 [ 我们就把currsString push 到 stack， stack 里面的 string 就会变成 prevString因为马上要遇到下一个 new string，当前数字也push 到 stack，然后currString ， currNum reset 准备保存将要遇到的 new string 和 new number

4. 当前char 是 ’] ‘: 遇到 ’]‘ 就代表当前string已经结束了，所以我们把 需要重复的数字从stack pop 出来 然后 repeat 当前sring 再 拼接上 prevString

//javascript

var decodeString = function(s) {
    let stack = [];
    let currString = "";
    let currNum = 0;

    for(let i =0; i<s.length;i++){
        let currChar = s[i]
        if(currChar === "["){
            stack.push(currString);
            stack.push(currNum);
            //reset currString
            currString = "";
            //reset currNum
            currNum = 0;
        }else if(currChar === "]"){
            let prevNum = stack.pop();
            let prevString  = stack.pop();
            currString= prevString + currString.repeat(prevNum);
        }else if(currChar>= "0" && currChar <= "9"){
            currNum = currNum*10 + Number(currChar);
        }else{
            currString+=currChar;
        }
    }
    return currString;
};
//TIME O(n) not sure
// space O(n) not sure

[Maschinist-LZY]

思路

先全部压入栈 然后识别到数字，遍历直达不是数字为止 对数字后的【】进行解码

代码(Python)

class Solution:
    def decodeString(self, s: str) -> str:
        stack1=list()
        length=len(s)
        i=length-1
        while i>=0:
            if s[i].isdigit()==False:
                stack1.append(s[i])
                i-=1
            else:
                num=''
                while i>=0 and s[i].isdigit():
                    num=s[i]+num
                    i-=1
                sub=''
                while stack1[-1]!=']':
                    tmp=stack1.pop()
                    if tmp!='[':
                        sub+=tmp
                stack1.pop()
                sub=int(num)*sub
                stack1.append(sub)

        stack1.reverse()
        return ''.join(stack1)

复杂度分析

时间：O(n)

空间：O(n)

[chang-you]

思路

递归模型 每次递归遇到"]“终止，ans记录返回的string, end 记录s的终止位置。

java code

class Solution {
    public String decodeString(String s) {
        char[] str = s.toCharArray();
        return process(str, 0).ans;
    }

    public static class Info {
        public String ans;
        public int end;

        public Info(String a, int e) {
            ans = a;
            end = e; // 哪个位置停
        }
    }

    // s[i....]  何时停？遇到   ']'  或者遇到 s的终止位置，停止
    // 返回Info (包含ans(返回的string) 和 end(算到了哪))
    public static Info process(char[] s, int i) {
        StringBuilder ans = new StringBuilder();
        int times = 0;
        while (i < s.length && s[i] != ']') {
            if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
                ans.append(s[i++]);
            } else if (s[i] >= '0' && s[i] <= '9') {
                //遇到数字 更新times
                times = times * 10 + s[i++] - '0';
            } else { // str[index] = '['
                Info next = process(s, i + 1);
                ans.append(timesString(times, next.ans));
                times = 0;
                i = next.end + 1;
            }
        }
        return new Info(ans.toString(), i);
    }

    public static String timesString(int times, String str) {
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < times; i++) {
            ans.append(str);
        }
        return ans.toString();
    }
}

复杂度

Time = O(n)
Space = O(n)
n为String长度

[falconruo]

思路:

1. 使用辅助栈存放：
   • repeat次数
   • 临时子串
   • 子串"["
2. 遇到']', 连续出栈直至栈顶元素为"[", 将所有的字符串拼接在一起，存放在一个字符串tmp
3. 将栈顶元素"["出栈
4. 继续取栈顶元素，此字符串为repeat次数k，将字符串tmp重复k次，存入新的子串ns并入栈
5. 循环完毕依次将栈st的子串取出，按照顺序插入返回字符串res

复杂度分析:

1. 时间复杂度: O(m), m为给定字符串s长度
2. 空间复杂度: O(n), n为decoded string长度

代码(C++):

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        stack<string> st;
        int n = s.length();

        for (int i = 0; i < n; ++i) {
            string tmp = "";
            if (isalpha(s[i])) {
                while (isalpha(s[i])) {
                    tmp += s[i];
                    ++i;
                }
                --i;
                st.push(tmp);
            } else if (isdigit(s[i])) {
                while (isdigit(s[i])) {
                    tmp += s[i];
                    ++i;
                }
                --i;
                st.push(tmp);
            } else if (s[i] == '[') {
                tmp += s[i];
                st.push(tmp);
            } else if (s[i] == ']') {
                while (st.top() != "[") { // add other alpha string into new
                    tmp.insert(0, st.top());
                    st.pop();
                }
                st.pop(); // "["

                int k = stoi(st.top()); // k
                st.pop();

                string ns = "";
                while (k--) // expand substring tmp by k times
                    ns += tmp;
                st.push(ns);
            }
        }

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

[ZiyangZ]

• Time O(maxCount * n) where maxCount is the maximum value of integer in s and n is the length of s.
• Space O(n).

class Solution {
    public String decodeString(String s) {
        StringBuilder ans = new StringBuilder();
        int count = 0;
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        for (char c: s.toCharArray()) {
            if (Character.isLetter(c)) {
                if (countStack.isEmpty()) ans.append(c);
                else {
                    stringStack.push(stringStack.pop().append(c));
                }
            }
            if (Character.isDigit(c)) {
                count = 10 * count + c - '0';
            }
            if (c == '[') {
                countStack.push(count);
                count = 0;
                stringStack.push(new StringBuilder());
            }
            if (c == ']') {
                int n = countStack.pop();
                StringBuilder sb = stringStack.pop();
                if (countStack.size() == 0) {
                    for (int i = 0; i < n; i++) {
                        ans.append(sb);
                    }
                } else {
                    StringBuilder cur = stringStack.pop();
                    for (int i = 0; i < n; i++) {
                        cur.append(sb);
                    }
                    stringStack.push(cur);
                }
            }
        }
        return ans.toString();
    }
}

[Yufanzh]

Intuition

(only figure out how to do it in iterative way) Use stack structure to help figuring out this problem. Use two variables to store: repeatStr to record letters to be repeated, repeatCnt: the repeated numbers, respectively. before we met with "]", we push every character encountered into stack individually. When we met with "]", we start to pop and record. At the step, we will need to check the types of element at the top of stack. if "[", pop out and not record; if letter, add to repeatStr, if numbers, add to repeatCnt as strings. Then the answer would be "repeatStr * int(repeatCnt)"

Algorithm in python 3

class Solution:
    def decodeString(self, s: str) -> str:
        #method-1:iterative way
        #check the char types: number?letter?left or right parenthese
        #left: push in stack; right: pop out of stack
        stack = []
        for c in s:
            if c == "]":
                #right parenthese start to triggle pop
                repeatStr = ""
                repeatCnt = ""
                while stack and stack[-1] != '[':
                    repeatStr = stack.pop() + repeatStr
                # pop out [
                stack.pop()
                while stack and stack[-1].isnumeric():
                    repeatCnt = stack.pop() + repeatCnt
                stack.append(repeatStr * int(repeatCnt))
            else:
                stack.append(c)
        return "".join(stack)

Complexity analysis

• Time complexity: O(N)
• Space complexity: O(N)

[mmboxmm]

思路

分为四种类型，数字，字符串，[ 和 ]。 前三种压栈，最后一个出栈。感觉很笨，需要学习一下！

代码

fun decodeString(s: String): String {
  if (s.isBlank()) return s

  val stack = ArrayDeque<String>()
  var i = 0
  while (i < s.length) {
    if (s[i].isDigit()) {
      val start = i
      while (++i < s.length && s[i].isDigit()) {
      }
      stack.addLast(s.substring(start, i))
    } else if (s[i].isLetter()) {
      val start = i
      while (++i < s.length && s[i].isLetter()) {
      }
      stack.addLast(s.substring(start, i))
    } else if (s[i] == '[') {
      stack.addLast("[")
      i++
    } else {
      val sb = StringBuilder()
      while (stack.isNotEmpty() && stack.last() != "[") {
        sb.insert(0, stack.removeLast())
      }
      stack.removeLast()
      val freq = stack.removeLast().toInt()
      stack.addLast(sb.repeat(freq))
      i++
    }
  }
  val res = StringBuilder()
  while (stack.isNotEmpty()) {
    res.insert(0, stack.removeLast())
  }
  return res.toString()
}

复杂度分析

• Time: O(len(s))
• Space: O(len(s))

[XinnXuu]

思路

遇到右括号前不断压栈，遇到右括号后开始出栈，先出栈所有字母直至非字母为止得到repeatStr，再继续出栈所有数字到非数字为止得到重复次数，根据重复次数拼接repeatStr并压入栈。循环结束后全部出栈即得到所求结果。

代码

class Solution {
    public String decodeString(String s) {

        Stack<Character> stack = new Stack<Character>();

        for (char c : s.toCharArray()){
            //把遇到]前的所有字符压入栈
            if(c != ']'){ 
                stack.push(c);
            } else{
                //遇到]后开始出栈
                //1.先取[]内字母
                StringBuilder letters = new StringBuilder();
                //弹出[]内字母
                while (!stack.isEmpty() && Character.isLetter(stack.peek())){
                    letters.insert(0, stack.pop());
                }

                String repeatStr = letters.toString();
                stack.pop(); //pop一次去除左括号[

                //2.开始取倍数数字
                StringBuilder num = new StringBuilder();
                while (!stack.isEmpty() && Character.isDigit(stack.peek())){
                    num.insert(0, stack.pop());
                }
                int repearCount = Integer.valueOf(num.toString());

                //3.根据倍数，拼接字符并压入栈中
                for ( ; repearCount > 0; repearCount--){
                    for (char ch : repeatStr.toCharArray()){
                        stack.push(ch);
                    }
                }
            }
        }
        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()){
            res.insert(0, stack.pop());
        }
        return res.toString();
    }
}

复杂度分析

• 时间复杂度：O(N),N为s长度
• 空间复杂度：O(N)

[siyuelee]

思路

递归

• 每次遇到[，我们进入下一个function。
• 每个function 返回 currentString
• 父function拿到子function返回的currentString， 乘上base从而加到自己的currentString
• 遇到]，当前function返回currentString
• 遇到字符，加到currentString
• 遇到数字，yongchar2digit提取数字

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        self.i = 0
        # 1. what to do before enter the function
        # 2. what does the function return
        # 3. what to do after the function
        def char2digit(s):
            base = 0
            i= 0
            while s[i].isdigit():
                base = 10 * base + int(s[i])
                i = i + 1
            return base,i

        def dfs(s):
            currentString = ""
            # "aa321s"
            while self.i < len(s):
                if s[self.i].isdigit():
                    base, length = char2digit(s[self.i:])
                    self.i = self.i + length
                    continue 
                elif s[self.i] == '[':
                    self.i += 1
                    ret = dfs(s)
                    currentString += base * ret
                elif s[self.i] == ']':
                    self.i += 1
                    return currentString
                else:
                    currentString += s[self.i]
                    self.i += 1
                # self.i += 1
            return currentString
        return dfs(s)

[heyqz]

代码

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

        for c in s:
            if c != "]":
                stack.append(c)
            else:
                substr = ""
                while stack[-1] != "[":
                    substr = stack.pop() + substr
                stack.pop() # pop out the "["

                k = ""
                while stack and stack[-1].isdigit(): 
                    k = stack.pop() + k
                stack.append(int(k) * substr)

        return "".join(stack)

复杂度

• time complexity: O(n)
• space complexity: O(n)

[laurallalala]

代码

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack = []
        for c in s:
            if c != "]":
                stack.append(c)
            else:
                last = stack[-1]
                cut = ""
                while last != "[":
                    stack.pop()
                    cut = last + cut
                    last = stack[-1]
                stack.pop()
                last = stack[-1]
                digits = ""
                while last.isdigit():
                    stack.pop()
                    digits = last + digits
                    if not stack:
                        break
                    last = stack[-1]
                stack.append(int(digits)*cut)
        return ''.join(stack)

复杂度

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

[pangjiadai]

思路

要点：有点类似于左括号、右括号用stack来解决的题目

• stack = [(str, num)] 用一个string参数来记录目前的string, 用num记录目前的number, 遇到“[”时入栈，遇到“]”出栈
• 直接用str = top[0] + str[1] * str来输出更新的string
• 如果是多位数，则num需要考虑进位

Python3

class Solution:
    def decodeString(self, s: str) -> str:
        stack = [] # stack = [(str, num)] 遇到“[”时入栈，遇到“]”出栈
        str = ""
        num = 0

        for char in s:
            if char.isdigit():
                num = num * 10 + int(char) #如果是多位数，要考虑进位*10
            elif char == '[':
                stack.append((str, num))
                str = ""
                num = 0
            elif char == ']':
                top = stack.pop()
                str = top[0] + str*top[1]
            else:
                str += char

        return str

复杂度：

time O(n), space O(n)

[absent1353]

思路：

辅助栈的思路

代码：

def decodeString(self, s: str) -> str:
        stack=[]
        length = len(s)
        i = length - 1
        while i>=0:
            if not s[i].isdigit():
                stack.append(s[i])
                i -= 1
            else:
                num = ''
                while s[i].isdigit() and i>=0:
                    num = s[i]+num
                    i -= 1
                sub = ''
                while stack[-1]!=']':
                    tmp = stack.pop()
                    if tmp != '[':
                        sub += tmp
                stack.pop()
                sub = int(num)*sub
                stack.append(sub)
        stack.reverse()
        return ''.join(stack)

复杂度：

时间复杂度 $O(N)$ 空间复杂度 $O(N)$

[kennyxcao]

394. Decode String

Intuition

• Use stack to keep track of each level of repeated encoded_string

Code

/**
 * @param {string} s
 * @return {string}
 */
const decodeString = function(s) {
  const stack = [];
  let str = '';
  let num = 0;
  for (const char of s) {
    if (/\d/.test(char)) { // if char is a digit
      num = num * 10 + parseInt(char, 10);
    } else if (char === '[') { // save current outer level info and reset for inner level
      stack.push([num, str]);
      num = 0;
      str = '';
    } else if (char === ']') { // retrieve outer level count and repeat the inner str
      const [count, outerStr] = stack.pop();
      str = outerStr + str.repeat(count);
    } else { // char is a letter
      str += char;
    }
  }
  return str;
};

Complexity Analysis

• Time: O(maxK * n)
• Space: O(sum(avgK * n))
• maxK = max k within k[encoded_string] patterns in s
• n = len(encoded_string)

[kidexp]

thoughts

very typical stack problem, we can iterate through the string,

1. each time we face a digit, we keep adding the digit to the stack
2. each time we face other char that ']' we just append to stack
3. each time we face ']' pop until ''[ to get string, then get num and multiple num with string and append to stack finally we will have join all strings in stack and return it

code

class Solution:
    def decodeString(self, s: str) -> str:
        """
        simplified version
        """
        stack = []
        i = 0
        for i in range(len(s)):
            if s[i].isdigit():
                if stack and type(stack[-1]) is int:
                    stack[-1] = stack[-1] * 10 + int(s[i])
                else:
                    stack.append(int(s[i]))
            elif s[i] == "]":
                temp_str = ""
                while stack and stack[-1] != "[":
                    temp_str = stack.pop() + temp_str
                if stack and stack[-1] == "[":
                    stack.pop()
                if stack and type(stack[-1]) is int:
                    repeat_num = stack.pop()
                    stack.append(temp_str * repeat_num)
            else:
                stack.append(s[i])
        return "".join(stack)

complexity

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

[banjingking]

思路

---

numStack: 要repeated多少遍的数字
strStack: 存a，当[a2[c]], a是不用repeat的
tail: 当前的string是什么
先loop每个char，判断char是digit，open bracket, close bracket, 遇到open bracket, 要将之前记录的string清空，push进去strStack, 遇到close bracket，就把numstack pop出来，乘上 tail

---

代码

public String decodeString(String s) {

    Deque<Integer> numStack = new ArrayDeque<>();
    Deque<String> strStack = new ArrayDeque<>();

    StringBuilder tail = new StringBuilder();
    int n = s.length();
    for(int i = 0; i < n; i++){
        char c = s.charAt(i);
        // if is number
        if(Character.isDigit(c)){
            // maybe not only one digit
            int num = c - '0';
            // see if next is digit
            while(i +1 <n && Character.isDigit(s.charAt(i+1))){
                num = num *10 + s.charAt(i+1) - '0';
                i++;
            }
            // put number into numStack
            numStack.push(num);
        }else if(c == '['){
            //put string which before the open bracket to the stack
            strStack.push(tail.toString());
            tail = new StringBuilder();
        }else if(c == ']'){
            StringBuilder tmp = new StringBuilder(strStack.pop());
            int repeatedTime = numStack.pop();
            for(int j =0; j < repeatedTime; j++){
                tmp.append(tail);
            }

            tail = tmp;
        }else{
            tail.append(c);
        }
    }
    return tail.toString();

}

[qyw-wqy]

代码

Java:

class Solution {
    int i = 0;
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        while (i < s.length()) {
            if (Character.isDigit(s.charAt(i))) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + s.charAt(i++) - '0';
                }
                i++; //skip '['
                String next = decodeString(s);
                while (num-- > 0) sb.append(next);
            } else if (s.charAt(i) == ']') {
                i++; // skip '['
                return sb.toString();
            } else {
                sb.append(s.charAt(i++));
            }
        }

        return sb.toString();
    }
}

Complexity: O(n)

[zjsuper]

idea all strings are separate by the num[], find each subpart string then merge

Class Solution:
    def decodeString(self, s:str) -> str:
        stack = []
        strs,nums = '',''
        for i in s:
            if i.isdigit():
                nums += i
            elif i.isalpha():
                strs += i
            elif i == '[':
                stack.append((strs,int(nums)))
                strs,nums = '',''
            elif i == ']':
                prev,num = stack.pop()
                strs = prev+num*strs
        return a

[freesan44]

思路

通过一个临时栈，从]符号开始倒数栈内的字符串然后进行拼接处理

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def decodeString(self, s: str) -> str:
        sList = list(s)
        stack = list()
        res = ""
        while len(sList) != 0:
            i = sList.pop(0)
            # print(i)
            if i == "]":#出栈
                tempStr = ""#找出栈内最后一个[]内的字符串
                while True:
                    j = str(stack.pop())
                    if j.isalpha() == True:
                        tempStr = j + tempStr
                    elif j == "[":
                        break
                tempInt = ""#找出栈内最后一个连续数字
                # print(stack, tempStr, tempInt,"-")
                while True:
                    try:
                        k = stack.pop()
                        if k.isnumeric() == True:
                            tempInt = k + tempInt
                        else:
                            stack.append(k)#如果是非数字，再次入栈
                            break
                    except:#用于边界条件【其实不稳固】
                        break
                # print(stack,tempStr,tempInt)
                stack.append(tempStr*int(tempInt))
                # print(stack)
            else:
                stack.append(i)
                # print(stack)
        return "".join(stack)

if __name__ == '__main__':
    # s = "3[a]2[bc]"
    # s = "3[a2[c]]"
    # s = "2[abc]3[cd]ef"
    # s = "abc3[cd]xyz"
    s = "100[leetcode]"
    result = Solution().decodeString(s)
    print(result)

复杂度分析

令 n 为数组长度。

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

[Francis-xsc]

思路

两个栈

代码

class Solution {
public:
    string decodeString(string s) {
        stack<int>num;
        stack<string>str;
        str.push("");
        int cnt=0,len=s.size();
        for(int i=0;i<len;i++)
        {
            if(isdigit(s[i]))
                cnt=cnt*10+s[i]-'0';
            else if(isalpha(s[i]))
                str.top()+=s[i];
            else if(s[i]=='[')
            {
                str.push("");
                num.push(cnt);
                cnt=0;
            }
            else if(s[i]==']')
            {
                int n=num.top();
                num.pop();
                string t=str.top();
                str.pop();
                for(int i=0;i<n;i++)
                    str.top()+=t;
            }
        }
        return str.top();
    }
};

复杂度分析

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

[kofzhang]

思路

用栈存储 倒序遍历字符串，遇到数值的下一个字符，处理字符串。

代码（Python3）

class Solution:
    def decodeString(self, s: str) -> str:
        stack=[]
        flag = False
        for c in s[::-1]+"/":

            if c.isdigit():
                flag = True
            if flag and not c.isdigit():    
                flag = False            
                temp = []
                while True:
                    t = stack.pop()
                    if t!="]":
                        temp.append(t)
                    else:
                        break
                temp = "".join(temp).split("[")
                stack.append(int(temp[0])*temp[1])
            stack.append(c)
        stack.pop()
        return "".join(stack[::-1])

复杂度

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

[now915]

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    let stack = []
    let multi = 0
    let res = ''

    for (const c of s) {
        if (c == '[') {
            stack.push([multi, res])
            multi = 0
            res = ''
        } else if (c == ']') {
            const last = stack.pop()
            let tmp = ''
            for (let i = 0; i < last[0]; i++) {
                tmp += res
            }
            res = last[1] + tmp
        } else if ('0' <= c && c <= '9') {
            multi = multi * 10 + (c - 0)
        } else {
            res += c
        }
    }
    return res
}; 

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

[tongxw]

思路

类似括号匹配，遍历字符串， 如果是数字，就计算当前数字； 如果是字符，入栈； 如果是左括号，先把当前计算好的数字入栈，再把左括号入栈； 如果是右括号，先把栈顶字符串依次出栈并拼接起来，直到碰到左括号。左括号出栈后，栈顶是重复次数，根据次数展开当前字符串后入栈。 遍历结束后把栈内所有已解码完成的字符串拼接起来。

代码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
  let stack = [];

  let num = 0;
  for (let i=0; i<s.length; i++) {
    if (s[i] >= '0' && s[i] <= '9') {
      num = num * 10 + (s[i] - '0');
    } else if (s[i] === '[') {
      stack.push(num);
      num = 0;
      stack.push(s[i]);
    } else if (s[i] === ']') {
      let str = '';
      while (stack[stack.length - 1] !== '[') {
        str = stack.pop() + str;
      }
      stack.pop(); // '['

      let temp = '';
      let repeat = stack.pop();
      while (repeat > 0) {
        temp += str;
        repeat--;
      }
      stack.push(temp);
    } else {
      // chars
      stack.push(s[i]);
    }
  }

  let ans = '';
  while (stack.length !== 0) {
    ans = stack.pop() + ans;
  }

  return ans;
};

TC: O(ans.length) SC: O(ans.length)

[ai2095]

LC394. Decode String

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

Topics

• Stack
• String

Similar Questions

Hard

• https://leetcode.com/problems/number-of-atoms/
• https://leetcode.com/problems/encode-string-with-shortest-length/

Medium

• https://leetcode.com/problems/brace-expansion/

Easy

思路

Scan s from left to right. When "[", Use stack to store processed string and num. When "]", pop processed string and num , and concatenate the new string.

代码 Python

class Solution:
    def decodeString(self, s: str) -> str:
        num, string, stack = 0, "", []
        for c in s:
            if c.isdigit():
                num = num*10 + int(c)
            elif c == "[":
                stack.append(string)
                stack.append(num)
                string = ""
                num = 0
            elif c.isalpha():
                string += c
            elif c == "]":
                pre_num = stack.pop()
                pre_string = stack.pop()
                string = pre_string + pre_num * string
        return string

复杂度分析

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

[SunStrongChina]

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"

解题思路： 碰到']'就开始退栈，知道退栈字符为'['为止 然后开始数字退栈，直到下一个数字不再是字符为止，最后提取该段解析结果，进栈

class Solution:
def decodeString(self, s: str) -> str:
l=0
str_array=[]
while l<len(s):
str_array.append(s[l])

        if s[l]==']':
            str1=''
            s2=str_array.pop()
            while s2!='[':
                s2=str_array.pop()
                if s2!='[':
                    str1=s2+str1

            numStr=''
            while len(str_array)>=1 and str_array[-1] in '01213456789':
                numStr=str_array.pop()+numStr
            str_array.append(str1*int(numStr))
        l+=1
    return ''.join(str_array)

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

[Dana-Dai]

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        stack<string> strs;
        stack<int> nums;
        int num = 0;
        for (int i = 0; i < s.size(); i ++) {
            if (s[i] >= '0' && s[i] <= '9')
                num = s[i] - '0' + num * 10;
            else if (s[i] == '[') {
                nums.push(num);
                num = 0;
                strs.push(res);
                res = "";
            }
            else if (s[i] >= 'a' && s[i] <= 'z') 
                res = res + s[i];
            else {
                int cur = nums.top();
                nums.pop();
                for (int i = 0; i < cur; i ++) 
                    strs.top() += res;
                res = strs.top();
                strs.pop();
            }
        }
        return res;
    }
};

时间复杂度和空间复杂度均要遍历一遍s，即O（N）

[liuyangqiQAQ]

class Solution {
    public String decodeString(String s) {
        StringBuilder strBud = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == ']') {
                StringBuilder str = new StringBuilder();
                while (true) {
                    char c = stack.pop();
                    if(c == '[') break;
                    else str.append(c);
                }
                int k = 0;
                //计算k
                int a = 1;
                while (!stack.isEmpty() && stack.peek() >= '0' && stack.peek() <= '9') {
                    k += a * (stack.pop() - '0');
                    a *= 10;
                }
                String s1 = str.toString();
                for (int j = 0; j < k; j++) {
                    for (int l = s1.length() - 1; l >= 0; l--) {
                        stack.push(s1.charAt(l));
                    }
                }
            }else {
                stack.push(s.charAt(i));
            }
        }
        while (!stack.isEmpty()) {
            strBud.append(stack.pop());
        }
        return strBud.reverse().toString();
    }
}

时间复杂度:O(n) n为字符串长度，因为拼接时时间复杂度会变成O(k * n)。但总的复杂度o(n)

空间复杂度:O(n) n为字符串长度

[AstrKing]

思路

利用栈的特性

代码

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();
                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();
    }
}

时间复杂度：O(n)

空间复杂度：O(n)