这是崔斯特的第一百零六篇原创文章

努力、奋斗

问题

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

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

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像3a或2[4]的输入。

示例

1
2
3

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

思路

输入:'3[a2[c]]'
初始化栈: 栈nums 存要重复的次数k,栈str 存字符串
遍历字符串:
指针指向字符'3',为数字
num暂存数字3
继续遍历,遇到字符'['
循环次数num入栈nums，空字符串res入栈str
nums: 3        res: ''
num置为0，str置空
继续遍历,遇到字符'a',为字母
空字符串res拼接字母'a',res='a'
继续遍历,遇到字符'2',为数字
num暂存数字2
继续遍历遇到字符'['
num入栈nums,res入栈str
nums: 3 -> 2    str: '' -> 'a'
num置为0，str置空
继续遍历,遇到字符'c',为字母
空字符串res拼接字母'c',res='c'
继续遍历遇到字符']'
nums弹出栈顶元素：当前字符串重复次数2
res = res*2 = 'cc'
str弹出栈顶元素'a'与res拼接并入栈:
res = 'a'+'cc'='acc'
str: '' -> 'acc'
继续遍历遇到字符']'
nums弹出栈顶元素：当前字符串重复次数3
res = res*3 = 'accaccacc'
str弹出栈顶元素空字符串''与res拼接并入栈:
res=''+'accaccacc'='accaccacc'
str: 'accaccacc'
结束返回res

注意：

由于重复次数可能大于10，所以暂存数字时要适当处理，如 num*10+当前数字
在c++里可以直接修改拼接字符，但Java不支持运算符重载，可以借助 StringBuilder 或 StringBuffer 类。
用栈暂存的逻辑与递归基本一致，可以理解为用递归实现栈。
python没有栈这种数据结构，可以用 list() 数组或双端队列 deque()
python可以只用一个栈以元组的形式重复次数和字符串，如(num,res)

利用栈

JAVA

public class Solution {
    public String decodeString(String s) {
        Stack<StringBuilder> str = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        StringBuilder res = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {
            if (c == '[') {
                str.push(res);
                nums.push(num);
                num = 0;
                res = new StringBuilder();
            } else if (c == ']') {
                StringBuilder stringBuilder = new StringBuilder();
                for (int i = nums.pop(); i > 0; i--) {
                    stringBuilder.append(res);
                }
                res = str.pop().append(stringBuilder);
            } else if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            } else {
                res.append(c);
            }
        }
        return res.toString();
    }
    public static void main(String[] args) {
        String s = "3[a]2[bc]";
        System.out.println(new Solution().decodeString(s));
    }
}

Python


class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, num = [], '', 0
        for i in s:
            if i.isdigit():
                num = num * 10 + int(i)
            elif i.isalpha():
                res += i
            elif i == '[':
                stack.append((res, num))
                res, num = '', 0
            else:
                last_str, this_num = stack.pop()
                res = last_str + this_num * res
        return res
c = Solution().decodeString('3[a2[c]]')  # aaabcbc
print(c)

Go

发现一种解法：倒序遍历字符串s，如果不是[则直接入栈；遇到[时，先找出[前边的数字nums表示为k，然后找出编码字符串encodedStr，重复k次入栈，跳过数字继续遍历

package main
import (
   "fmt"
   "strconv"
   "strings"
)
func decodeString(s string) string {
   stack := make([]string, 0)
   for i := len(s) - 1; i >= 0; {
      if s[i] == '[' {
         nums := make([]string, 0)
         for j := i - 1; j >= 0; j-- {
            if s[j] >= '0' && s[j] <= '9' {
               nums = append(nums, string(s[j]))
            } else {
               break
            }
         }
         reverse(nums)
         k, _ := strconv.Atoi(strings.Join(nums, ""))
         encodedStr := make([]string, 0)
         for stack[len(stack)-1] != "]" {
            encodedStr = append(encodedStr, stack[len(stack)-1])
            stack = stack[:len(stack)-1]
         }
         stack = stack[:len(stack)-1]
         reverse(encodedStr)
         for j := 0; j < k; j++ {
            stack = append(stack, encodedStr...)
         }
         i -= len(nums)
      } else {
         stack = append(stack, string(s[i]))
      }
      i -= 1
   }
   reverse(stack)
   return strings.Join(stack, "")
}
func reverse(arr []string) {
   length := len(arr)
   for i := 0; i < length/2; i++ {
      arr[i], arr[length-i-1] = arr[length-i-1], arr[i]
   }
}
func main() {
   s := "3[a]2[bc]"
   r := decodeString(s)
   fmt.Println(r)
}

惊了惊了，这么牛逼

利用递归

JAVA

将 s.length() 的值以参数传递，减少重复调用 length() 造成的时间损耗

public class Solution {
    private int i = -1;
    public String decodeString(String s) {
        return dfs(s.toCharArray(), s.length()).toString();
    }
    private StringBuilder dfs(char[] chars, int len) {
        int num = 0;
        StringBuilder str = new StringBuilder();
        while (++i < len) {
            if (chars[i] >= '0' && chars[i] <= '9') {
                num = num * 10 + (chars[i] - '0');
            } else if (chars[i] == '[') {
                StringBuilder tmp = dfs(chars, len);
                while (--num >= 0) {
                    str.append(tmp);
                }
                num = 0;
            } else if (chars[i] == ']') {
                return str;
            } else {
                str.append(chars[i]);
            }
        }
        return str;
    }
    public static void main(String[] args) {
        String s = "3[a]2[bc]";
        System.out.println(new Solution().decodeString(s));
    }
}

Python

class Solution:
    i = -1
    def decodeString(self, s: str) -> str:
        res, num = '', 0
        while self.i < len(s) - 1:
            self.i += 1
            if s[self.i].isdigit():
                num = num * 10 + int(s[self.i])
            elif s[self.i].isalpha():
                res += s[self.i]
            elif s[self.i] == '[':
                res += self.decodeString(s) * num
                num = 0
            else:
                return res
        return res
if __name__ == '__main__':
    assert Solution().decodeString('3[a]2[bc]') == 'aaabcbc'
    assert Solution().decodeString('3[a2[c]]') == 'accaccacc'
    assert Solution().decodeString('2[abc]3[cd]ef') == 'abcabccdcdcdef'