394. Decode String

发表于 | 分类于 | |

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

1
2
3
4
> s = "3[a]2[bc]", return "aaabcbc".
> s = "3[a2[c]]", return "accaccacc".
> s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
>

题意：按照加密规则解密字符串。

​ 初看这道题时就感觉跟本科学数据结构时的表达式运算差不多，因为有嵌套关系并且是里层的先解密，即满足后进先出的特点，所以就需要利用到栈。但是在实验室思绪比较混乱，想了两小时愣是没做出来，就是在消耗时间，不够专注。

​ 晚上回宿舍后静下心来来想不到半小时就把思路和代码都理清了！可见，宁静致远！

​ 其实最主要就是维护好两个栈，一个数字的nums和需要被解密的字符串chars。

​ 每次读进来一个字符c=s[i]，这时c无非就以下几种情况，分别处理。

  1. “[“：把[前面的数字入nums栈,然后加个空字符“”入栈，代表以后的字符串是需要被解密的（即需要被解密的字符串又多了一个了）。

  2. “]”：从nums取栈头n并退栈，从chars取栈str头并退栈，计算出str解密后的endcode，将j解密后encode接到chars栈头字符串的后面，等待一下次解密。

  3. 数字：加到数字字符串strNum (数字并不是个位数，有可能多位，如100)

  4. 字母：将字母接到chars栈头字符串的后面，等待解密。

    当把读进来的字符串s挨个字符都处理完之后，chars栈头就是最后答案了！

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
59
60
61
62
//
// Created by cpz on 2017/11/22.
//

#include "head.h"

class Solution {
public:
    string decodeString(string s)
    {
        stack<string> chars;
        chars.push("");
        stack<int> nums;
        string c;
        string encode = "";
        string str;
        int n;
        string strOfNums = "";
        for (int i = 0; i < s.size(); ++i)
        {
            c = s[i];
            if (c == "[")
            {

                n = atoi(strOfNums.c_str());
                nums.push(n);
                strOfNums = "";

                chars.push("");
            } else if (c == "]")
            {
                str = chars.top();
                chars.pop();
                n = nums.top();
                nums.pop();
                encode = "";
                for (int j = 0; j < n; ++j)
                {
                    encode += str;
                }
                encode = chars.top() + encode;
                chars.pop();
                chars.push(encode);
            } else if (has_only_digits(c))//num
            {
                strOfNums += c;
            } else//字母
            {
                encode = chars.top();
                chars.pop();
                encode += c;
                chars.push(encode);
            }
        }
        return chars.top();
    }

    bool has_only_digits(const string s)
    {
        return s.find_first_not_of("0123456789") == string::npos;
    }
};