LeetCode 300. Longest Increasing Subsequence 最长上升子序列

Posted on | In

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].

示例:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "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
class Solution {
int index = 0;
public:

    string decodeString(string s) {
        int digit = 1;
        int previousIsDigit = false;
        string finalstr = "";
        string localstr = "";

        for (; index < s.size(); index++) {
            if (s[index] == ']')
                return finalstr;
            if (isdigit(s[index])) {
                if (!previousIsDigit)
                    digit = s[index] - '0';
                else
                    digit = digit * 10 + (s[index] - '0');
                previousIsDigit = true;
            }
            else if ((s[index] == '[')) {
                previousIsDigit = false;
                index ++;
                string str = decodeString(s);
                for (int j = 0; j < digit; j++) {
                    finalstr += str;
                }
                digit = 1;
                while (index < s.size() && s[index] != ']') 
                    index++;       
            }
            else {
                previousIsDigit = false;
                while(isalpha(s[index]) && index < s.size()) {
                    localstr += s[index];
                    index++;
                }
                index--;
                for (int j = 0; j < digit; j++) {
                    finalstr += localstr;
                }
                digit = 1;
                localstr = "";
            }

            }
        return finalstr; 
    }
};