[Leetcode]394. Decode String(C++)

题目描述

Given an encoded string, return its 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].

例子

例子 1

Input: s = "3[a]2[bc]" Output: "aaabcbc"

例子 2

Input: "3[a2[c]]" Output: "accaccacc"

例子 3

Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef"

Constraints

1 <= s.length <= 30

s consists of lowercase English letters, digits, and square brackets '[]'.

s is guaranteed to be a valid input.

All the integers in s are in the range [1, 300].

解题思路

首先观察以下加密后字符串的组成部分:

数字：表示下一部分字符串的重复次数
[：后面一定跟着字母，表示要重复的字母
]：表示要重复部分字符串的结束标志
字母：有两种情况
- 被[] 包围：起始位置一定在 [ 后面，表示这部分字符串要重复
- 不被 [] 包围：这部分字符串不会重复

由于 [] 可以嵌套，所以需要用栈的思路来解密，具体思路是，遍历字符串：

遇到数字，遍历找到数字的结尾：将该数字压入数字栈中
遇到 [，表示重复子串的起点，遍历将该子串压入子串栈中
遇到 ]，表示重复子串的结尾，冲数字栈和子串栈中分别去除栈顶元素构建出重复后的子串，此时判断子串栈是否为空：

如果为空：表示要重复的部分已经结束可以将该重复后的字符串添加在返回串的末尾
否则需要将其连接至子串栈中的栈顶元素

遇到字母：由于不是跟在 [ 后面，因此不需要重复，当做重复后的子串参照步骤 3 处理

代码如下：

#include <stack>
#include <string>

class Solution {
public:
    std::string decodeString(std::string s) {
        std::string res = "";
        std::stack<int> count_stk;
        std::stack<std::string> str_stk;
        int ptr = 0;
        while (ptr < s.length()) {
            if (std::isdigit(s[ptr])) {
                int count = 0;
                while (ptr < s.length() && std::isdigit(s[ptr])) {
                    count *= 10;
                    count += s[ptr] - '0';
                    ptr++;
                }
                count_stk.push(count);
            } else if (s[ptr] == '[') {
                ptr++;
                std::string temp_str = "";
                while (ptr < s.length() && std::isalpha(s[ptr])) {
                    temp_str += s[ptr];
                    ptr++;
                }
                str_stk.push(temp_str);
            } else if (s[ptr] == ']') {
                std::string new_str = "";
                for (int i = 0; i < count_stk.top(); ++i) {
                    new_str += str_stk.top();
                }
                str_stk.pop();
                count_stk.pop();

                if (count_stk.empty()) {
                    res += new_str;
                } else {
                    str_stk.top() += new_str;
                }
                ptr++;
            } else {
                if (std::isalpha(s[ptr])) {
                    if (str_stk.empty()) {
                        res += s[ptr];
                    } else {
                        str_stk.top() += s[ptr];
                    }
                }
                ptr++;
            }
        }

        return res;
    }
};

时间复杂度: O(n)
空间复杂度: O(n)

GitHub 代码同步地址： 394.DecodeString.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions