leetcode394：字符串解码

题目链接

leetcode

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

C++ 代码

#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

/*
    把字母、数字和括号作为独立的 TOKEN，用栈来维护这些 TOKEN。
    注意：可能出现括号嵌套的情况。
    
    具体做法：遍历这个栈
        若当前字符为数字，则拼接出完整的数字；
        若当前字符为字母，则拼接出完整的字符串；
        若当前字符为左括号，则数字和字母都进栈；
        若当前字符为右括号，则字母和数字都出栈，根据字符串和次数拼接出新的字符串。
    重复如上操作，将栈中的元素按照从栈底到栈顶的顺序拼接，得到答案。

    时间复杂度：O(n)
        假设解码后的字符串长度为 n，除了遍历一次原字符串 s，
        将解码后的字符串中的每个字符都入栈，最终拼接进答案，
        时间复杂度为 O(n)。
    空间复杂度：O(n)
        栈维护 TOKEN，栈的大小等于字符串长度，空间复杂度为 O(n)。
*/
class Solution {
public:
    string decodeString(string s) {
        string num = "", sign = "";
        stack<string> stk;

        for (const char& c : s) {
            if (isdigit(c)) {
                num += c;
            } else if (isalpha(c)) {
                sign += c;
            } else if (c == '[') {
                stk.push(num);
                stk.push(sign);
                num = "";
                sign = "";
            } else if (c == ']') {
                string letters = stk.top(); stk.pop();
                string times = stk.top(); stk.pop();
                int iTimes = atoi(times.c_str());
                for (int i = 0; i < iTimes; i++) {
                    letters += sign;
                }
                sign = letters;
            }
        }

        return sign;
    }
};

/*
    思路同上
*/
class Solution_1 {
public:
    string decodeString(string s) {
        stack<pair<string, int>> stk;
        string str = "";
        int num = 0;

        for (const char& c : s) {
            if (isdigit(c)) {
                num = num * 10 + (c - '0');
            } else if (isalpha(c)) {
                str += c;
            } else if (c == '[') {
                stk.push({str, num});
                str = "";
                num = 0;
            } else if (c == ']') {
                auto top = stk.top(); stk.pop();
                string repeatString;
                for (int i = 0; i < top.second; i++) {
                    repeatString += str;
                }
                str = top.first + repeatString;
            }
        }

        return str;
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = {
        "3[a]2[bc]",
        "3[a2[c]]",
        "2[abc]3[cd]ef",
        "abc3[cd]xyz"
    };

    for (int i = 0; i < s_cases.size(); i++) {
        string s = s_cases[i];
        string result = solution.decodeString(s);

        cout << "Input: s = " << "\"" << s << "\"" << endl;
        cout << "Output: " << "\"" << result << "\"" << endl;
    }

    return 0;
}