11

[wangzichengTech]

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"

关键点

• 掌握递归的使用，每个子字符串就是一层递归，利用递归层层深入然后再返回想得到的字符串。

代码

• 语言支持：Java

Java Code:

package com.wzc;

public class solution03 {
    public static void main(String[] args) {
        solution03 solution03 = new solution03();
        String s = "3[a2[c]]3[b]";
        String s1 = solution03.decodeString(s);
        System.out.println(s1);
    }
    private int index = 0;
    public String decodeString(String s) {
        String str = recursive(s);
        return str;
    }

    private String recursive(String s) {
        StringBuilder builder = new StringBuilder();
        while (index < s.length()) {
//        提取当前字母
            char cur = s.charAt(index);
            index++;
            if (cur >= '0' && cur <= '9') {
                int num = cur - '0';
                while (s.charAt(index)>='0'&&s.charAt(index)<='9'){
                    num = 10*num + (s.charAt(index)-'0');
                    index++;
                }
//                递归获得子串
                String str = recursive(s);
//                将子串复制相同的次数
                for (int i = 0; i < num; i++) {
                    builder.append(str);
                }
            }else if (cur == '['){

            }else if (cur == ']'){
//                相当于子串建立完成退出循环
                break;
            }else{
//                如果是普通字符则拼接
                builder.append(cur);
            }
        }
        return builder.toString();
    }
}

复杂度分析

令 n 为数组长度。

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

[simbafl]

nonono

[z1ggy-o]

请利用已有的 issue 进行打卡。