题目

题目地址：https://leetcode-cn.com/problems/decode-string/

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

编码规则为: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".

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package com.jarome.leetcode.test1.summary;

import java.util.Stack;

public class SolutionDecodeString {

    public String decodeString(String s) {
        Stack<String> stack = new Stack<>();
        String numStrTemp = "";
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            String str = String.valueOf(c);
            // 判断是不是数字
            if (Character.isDigit(c)) {
                numStrTemp = numStrTemp + str;
                continue;
            } else {
                stack.push(numStrTemp);
                numStrTemp = "";
            }
            if ("]".equals(str)) {
                String base = "";
                while (true) {
                    String pop = stack.pop();
                    if ("[".equals(pop)) {
                        // 计算
                        // 按照题意，这个时候的栈顶元素一定是数字
                        Integer num = Integer.valueOf(stack.pop());
                        String newStr = "";
                        for (int j = 0; j < num; j++) {
                            newStr = newStr + base;
                        }
                        stack.push(newStr);
                        break;
                    }
                    base = pop + base;
                }
            } else {
                stack.push(str);
            }
        }
        String res = "";
        while (!stack.isEmpty()) {
            res = stack.pop() + res;
        }
        return res;
    }

    public static void main(String[] args) {
        SolutionDecodeString sd = new SolutionDecodeString();
        // String s = "2[abc]3[cd]ef";
        // String s = "3[a2[c]]";
        String s = "100[leetcode]";
        String res = sd.decodeString(s);
        System.out.println(res);
    }
}

执行情况：

  • 执行用时: 2ms
  • 内存消耗: 37.9MB