Leetcode 394.字符串解码

题目描述：

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

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

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

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

示例 1：

1
2

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

示例 2：

1
2

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

示例 3：

1
2

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

示例 4：

1
2

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

链接：

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

题目分析

  根据编码的规则和给出的示例，我们可以看到这个编码是存在着嵌套的结构的，那么我们可以考虑使用递归的方法进行处理。对于我们遇到的每一个数字，都意味着出现了 k[encoded_string] 结构。那么我们可以将这个结构作为一个整体进行处理，然后返回一个处理好的字符串，交给外层的嵌套结构进行处理。为了方便，我们可以直接将待处理的原字符串和正在处理的下标使用这个类的成员变量表示，这样就可以在各个函数中直接使用。
  读取 k 的函数是 getDigits()，可以读入一位或多位的数字串，并转化成整型变量表示，最后下标会停留在下一位，也就是 '[' 上。
  读取字符串的函数是 getString()。结束条件是到达字符串结尾或者遇到了 ']'。读取的时候我们需要先判断是不是数字，如果是的话就获取到数字 k 也即我们的重复次数。然后停留在 '[' 上需要跳过。而我们的循环体就要使用递归结果继续调用 getString() 获取。获取后是停留在 ']' 上的，我们也要跳过。然后我们将获取到的字符串重复 k 次，这样就处理好了一个 k[encoded_sting] 结构。如果读取到的是字母，那么我们将字母添加上去即可。
  而这样一次处理只是处理好了一个 k[encoded_string] 结构或者是一个字母，而我们可能有多个这样的结构顺序排列，所以返回的结果应该是处理好的这个串接下一次处理 ret + getString()。
  这样可以处理并列或者嵌套的结构，最后在主函数中给两个成员变量赋初始值并调用最外层的一个 getString() 函数即可得到最终结果。

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

class Solution {
    int ptr;
    string src;

    int getDigits(){
        int num = 0;
        while(isdigit(src[ptr])){
            num *= 10;
            num += src[ptr] - '0';
            ptr++;
        }
        return num;
    }

    string getString(){
        if(ptr == src.size() || src[ptr] == ']'){
            return "";
        }
        string ret;
        if(isdigit(src[ptr])){
            int times = getDigits();
            ptr++; // 跳过数字之后的 '['
            string loopBody = getString();
            ptr++; // 跳过字母之后的 ']'
            while(times--){
                ret += loopBody;
            }
        }
        else if(isalpha(src[ptr])){
            ret += src[ptr++];
        }
        
        return ret + getString();
    }
public:
    string decodeString(string s) {
        src = s;
        ptr = 0;
        return getString();
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是解码后的字符串长度。我们对原字符串进行一次遍历进行处理，而最后得到的字符串就是一个字符一个字符添加上去的。
  空间复杂度：$O(n)$，其中 $n$ 是解码后的字符串长度。主要是栈递归的深度，还有嵌套过程中保存的临时字符串，栈递归的深度和临时字符串的长度都不会超过解码后字符串的长度。