【leetcode】394 Decode String

发表于 | 分类于 ，

解码字符


描述

将形如 2[ad] 的字符解串码成 adad,数字代表次数，方括号的内容代表被重复的部分。

样例

样例1

1
2
输入: 3[a]2[bc]
输出: aaabcbc

样例2

1
2
输入: 3[a2[c]]
输出: accaccacc

思路

可以利用栈解决，建立两个栈，一个保存字符，一个保存数字。这里要注意对重复部分的处理，因为中括号可能里面还有中括号，这时候要将字符重新压回栈内。同时注意字符不一定外面有中括号，字符包括小写和大写字符。这道题也可以用递归解决。

代码

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
class Solution {
public:
    string decodeString(string s) {
        stack<char> stackstr;
        stack<int> stacknumber;
        string result="";
        int num = 0;
        for (int i = 0;i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                num = num *10 + (s[i] - '0');
            }
            else if (s[i]=='[') {
                stacknumber.push(num);
                num = 0;
                stackstr.push('[');
            }
            else if (s[i] >= 'a'&& s[i] <= 'z') {
                stackstr.push(s[i]);
            }
            else if (s[i] >= 'A'&& s[i] <= 'Z') {
                stackstr.push(s[i]);
            }
            else if (s[i] == ']') {
                int n = stacknumber.top();
                stacknumber.pop();
                string str ="";
                while (!stackstr.empty()) {
                    char c = stackstr.top();
                    if (c != '[') {
                        str = c + str;
                        stackstr.pop();
                    }
                    else {
                        stackstr.pop();
                        break;
                    }
                }
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < str.size(); k++) {
                        stackstr.push(str[k]);
                    }
                }
            }
        }
        while (!stackstr.empty()) {
            result = stackstr.top()+ result;
            stackstr.pop();
        }
        return result;
    }
};

参考代码

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
class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return helper(s, i);
    }

    string helper(string &s, int &i) {
        string res;
        while(i < s.size() && s[i] != ']') {
            if(isdigit(s[i])) {
                int n = 0;
                while( i < s.size() && isdigit(s[i])) {
                    n = n*10 + (s[i] - '0');
                    i++;
                }
                i++;
                string temp = helper(s, i);
                while(n > 0) {
                    res += temp;
                    n--;
                }
                i++;
            } else {
                res += s[i++];
            }
        }
        return res;
    }
};

参考

原题链接