递归解码一个以计数后跟子字符串编码的字符串

在这个问题中，我们需要通过重复添加总计数次数来解码给定的字符串。

我们可以采用三种不同的方法来解决问题，并且可以使用两个堆栈或一个堆栈来解决问题。另外，我们可以在不使用两个堆栈的情况下解决问题。

问题陈述 - 我们给出了一个字符串 str ，其中包含左括号和右括号、字母和数字字符。我们需要递归地解码字符串。

以下是解码字符串的模式或规则。

• [chars] - “chars”应该在结果字符串中出现 count 次。

示例

输入

str = "2[d]3[c2[n]]";

输出

ddcnncnncnn

说明

• 首先，我们解码 2[n]，得到“2[d]3[cnn]”。

• 接下来，我们解码 3[cnn]。所以，我们得到“2[d]cnnncnncnn”。

• 接下来，我们解码 2[d]。所以，我们得到“ddcnnncnncnn”。

输入

5[i]

输出

iiiii

解释- 当我们解码给定的字符串时，我们得到 5 个“I”。

输入

3[fg]

输出

fgfgfg

解释- 当我们解码输入字符串时，我们得到“fg”3次。

方法 1

我们将使用两个堆栈来解决此方法中的问题。当我们得到一个左括号时，我们将其推入堆栈。此外，当我们获取数字字符时，我们将所有数字字符附加到一个有效的正整数并将它们添加到整数堆栈中。之后，当我们得到右括号时，我们从堆栈中弹出整数和字符。

算法

第 1 步- 定义“instSt”堆栈来存储数字，定义“strSt”来存储字符串字符和左括号。此外，初始化“answer”以存储结果字符串，初始化“tempStr”以存储临时字符串。

第 2 步- 开始遍历字符串。

第 3 步- 如果当前字符是数字，则用 0 初始化“num”以存储数字。

步骤 3.1 − 如果第 p^th 索引处的字符是数字，则遍历字符串，直到得到字母字符或括号。在循环中，将“num”的先前值乘以 10，并将当前数字添加到其中。

步骤 3.2− 将“p”的值增加 1。

步骤 3.3 - 将数字值推送到“instSt”堆栈。

步骤 4 - 如果第 p 个索引处的字符是右括号，请按照以下步骤操作。

步骤 4.1- 用空字符串初始化“temp_str”。之后，如果‘instSt’不为空，则从堆栈中弹出顶部整数。

步骤 4.2 - 现在，使用循环，直到我们得到左括号或堆栈从“strSt”堆栈变空。另外，将字符附加到“temp_str”。

步骤 4.3 - 如果我们由于“[”而停止对角色进行大便，请将其删除。

步骤 4.4 - 接下来，我们需要在“answer”字符串中附加“temp_Str”“num”次。

步骤 4.5 - 将“answer”字符串的每个字符插入“strSt”堆栈中，并使用空字符串重新初始化它。

步骤 5 − 如果当前字符是左括号，请按照以下步骤操作。

步骤 5.1 − 如果前一个字符是数字，则将“[”推入堆栈“StrSt”。否则，将“[”压入 StrSt 堆栈，并将 1 压入“instSt”堆栈。

第 6 步− 如果我们得到一个字母字符，则将其推入“strSt”堆栈。

第 7 步- 最后，使用循环从“strSt”堆栈中删除所有字符，附加到“answer”字符串，然后返回它。

示例

#include <bits/stdc++.h>
using namespace std;

string decodeTheString(string alpha) {
    stack<int> instSt;
    stack<char> StrSt;
    string tempStr = "", answer = "";
    // Iterate the string
    for (int p = 0; p < alpha.length(); p++) {
        int num = 0;
        // If we find the number, extract the number and push it to the stack
        if (alpha[p] >= '0' && alpha[p] <= '9') {
            // Making iterations until we get an alphabetic character
            while (alpha[p] >= '0' && alpha[p] <= '9') {
                num = num * 10 + alpha[p] - '0';
                p++;
            }
            p--;
            instSt.push(num);
        }
        // If the character at the pth index is closing bracket
        else if (alpha[p] == ']') {
            tempStr = "";
            num = 0;
            // Pop the number from the stack
            if (!instSt.empty()) {
                num = instSt.top();
                instSt.pop();
            }
            // Pop the character until we get the opening bracket
            while (!StrSt.empty() && StrSt.top() != '[') {
                tempStr = StrSt.top() + tempStr;
                StrSt.pop();
            }
            // remove the opening bracket
            if (!StrSt.empty() && StrSt.top() == '[')
                StrSt.pop();
            // Append string to answer for num times
            for (int j = 0; j < num; j++)
                answer = answer + tempStr;
            // Insert the updated string again into the stack
            for (int j = 0; j < answer.length(); j++)
                StrSt.push(answer[j]);
            answer = "";
        }
        // If the character at the pth index is an opening bracket
        else if (alpha[p] == '[') {
            if (alpha[p - 1] >= '0' && alpha[p - 1] <= '9') {
                StrSt.push(alpha[p]);
            } else {
                StrSt.push(alpha[p]);
                instSt.push(1);
            }
        } else {
            // Push alphabetic character in the string stack.
            StrSt.push(alpha[p]);
        }
    }
    // Pop all the elements, make a string, and return.
    while (!StrSt.empty()) {
        answer = StrSt.top() + answer;
        StrSt.pop();
    }
    return answer;
}
// starting code
int main() {
    string str = "2[d]3[c2[n]]";
    cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl;
    return 0;
}

输出

The resultant string after decoding it is - ddcnncnncnn

时间复杂度− O(n^2)，因为我们遍历字符串并不断向堆栈推送和弹出元素。

空间复杂度− 在堆栈中存储元素的 O(n)。

方法2

我们将在这种方法中不使用堆栈来解决问题。另外，我们将使用reverse()方法来反转字符串。

算法

第 1 步- 开始迭代字符串。

第 2 步− 如果第 i 个字符是“]”，则将其推入“answer”字符串。否则，请按照以下步骤操作。

第 3 步- 使用空字符串初始化“temp_Str”。

第 4 步- 继续遍历“answer”字符串，直到该字符串为空或找到“[”字符。另外，继续从“answer”字符串中弹出最后一个字符并将其附加到“temp_Str”字符串中。

第 5 步- 当我们从找到“]”括号的位置向后遍历时，反转“temp_Str”字符串。

第 6 步- 从“answer”字符串中删除最后一个字符以删除“[”字符。

第 7 步- 如果“答案”字符串顶部包含数字，则使用数字生成一个整数，并将其存储在 number 变量中。

第 8 步- 反转数字字符串。

第 9 步- 使用 stoi() 方法将字符串转换为数字。

步骤 10 - 将 temp_Str 字符串附加到答案字符串“number”次。

第 11 步- 返回“答案”字符串。

示例

#include <bits/stdc++.h>
using namespace std;

string decodeTheString(string alpha) {
    string answer = "";
    // iterate the string characters
    for (int i = 0; i < alpha.length(); i++) {
        // for all other characters except the closing bracket
        if (alpha[i] != ']') {
            answer.push_back(alpha[i]);
        } else {
            // Extract the substring lying within the pair
            string temp_str = "";
            // Keep on popping characters until '[' is found.
            while (!answer.empty() && answer.back() != '[') {
                temp_str.push_back(answer.back());
                answer.pop_back();
            }
            // get original string by reversing the string
            reverse(temp_str.begin(), temp_str.end());
            // open bracket removal
            answer.pop_back();
            // get integer value before the '[' character
            string number = "";
            // get the number before opening bracket
            while (!answer.empty() && answer.back() >= '0' && answer.back() <= '9') {
                number.push_back(answer.back());
                answer.pop_back();
            }
            // reverse number string
            reverse(number.begin(), number.end());
            // convert string to integer
            int numInt = stoi(number);
            for (int p = 0; p < numInt; p++) {
                answer += temp_str;
            }
        }
    }
    return answer;
}
int main() {
    string str = "2[d]3[c2[n]]";
    cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl;
    return 0;
}

输出

The resultant string after decoding it is − ddcnncnncnn

时间复杂度− O(N^2)，因为我们遍历字符串并在循环内使用reverse()方法。

空间复杂度− O(N) 来存储数字和临时字符串。