对以 Count 和 Substring 形式递归编码的字符串进行解码
在此问题中，我们需要通过重复添加总 count 次数来解码给定的字符串。
我们可以采用三种不同的方法来解决问题，并且可以使用两个堆栈或一个堆栈来解决问题。此外，我们可以在不使用两个堆栈的情况下解决问题。
问题陈述 - 我们给出了一个包含开括号和闭括号、字母和数字字符的字符串 str。我们需要递归地解码该字符串。
以下是解码字符串的模式或规则。
<count>[chars] - "chars" 应在结果字符串中出现 count 次。
示例
输入
str = "2[d]3[c2[n]]";
输出
ddcnncnncnn
解释
首先，我们解码 2[n]，得到"2[d]3[cnn]"。
接下来，我们解码 3[cnn]。因此，我们得到"2[d]cnncnncnn"。
接下来，我们解码 2[d]。因此，我们得到了"ddcnncnncnn"。
输入
5[i]
输出
iiiii
解释− 当我们解码给定的字符串时，我们得到 5 个"I"。
输入
3[fg]
输出
fgfgfg
解释− 当我们解码输入字符串时，我们得到 3 次"fg"。
方法 1
我们将使用两个堆栈来解决问题。当我们得到一个左括号时，我们将其推入堆栈。此外，当我们得到数字字符时，我们将所有数字字符附加为一个有效的正整数并将它们添加到整数堆栈中。之后，当我们得到右括号时，我们从堆栈中弹出整数和字符。
算法
步骤 1 - 定义"instSt"堆栈以存储数字，定义"strSt"以存储字符串字符和左括号。此外，初始化"answer"以存储结果字符串，初始化"tempStr"以存储临时字符串。
步骤 2 - 开始遍历字符串。
步骤 3 − 如果当前字符是数字，则用 0 初始化"num"以存储数字。
步骤 3.1 − 如果第 p 个索引处的字符是数字，则遍历字符串，直到我们得到一个字母字符或括号。在循环中，将"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 = "";
// 迭代字符串
for (int p = 0; p < alpha.length(); p++) {
int num = 0;
// 如果找到该数字，则提取该数字并将其推送到堆栈
if (alpha[p] >= '0' && alpha[p] <= '9') {
// 不断迭代，直到得到一个字母字符
while (alpha[p] >= '0' && alpha[p] <= '9') {
num = num * 10 + alpha[p] - '0';
p++;
}
p--;
instSt.push(num);
}
// 如果第 p 个索引处的字符是右括号
else if (alpha[p] == ']') {
tempStr = "";
num = 0;
// 从堆栈中弹出数字
if (!instSt.empty()) {
num = instSt.top();
instSt.pop();
}
// 弹出字符直到我们得到左括号
while (!StrSt.empty() && StrSt.top() != '[') {
tempStr = StrSt.top() + tempStr;
StrSt.pop();
}
// 删除左括号
if (!StrSt.empty() && StrSt.top() == '[')
StrSt.pop();
// 将字符串附加到 answer num 次
for (int j = 0; j < num; j++)
answer = answer + tempStr;
// 将更新后的字符串再次插入堆栈
for (int j = 0; j < answer.length(); j++)
StrSt.push(answer[j]);
answer = "";
}
// 如果第 p 个索引处的字符是左括号
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 {
// 将字母字符推送到字符串堆栈中。
StrSt.push(alpha[p]);
}
}
// 弹出所有元素，创建一个字符串，然后返回。
while (!StrSt.empty()) {
answer = StrSt.top() + answer;
StrSt.pop();
}
return answer;
}
// 起始代码
int main() {
string str = "2[d]3[c2[n]]";
cout << "解码后的结果字符串为 - " << decryptTheString(str) << endl;
return 0;
}
输出
解码后的结果字符串为 - 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 - 如果"answer"字符串顶部包含数字，则使用数字创建一个整数，并将其存储在数字变量中。
步骤 8 - 反转数字字符串。
步骤 9 - 使用 stoi() 方法将字符串转换为数字。
步骤 10 - 将 temp_Str 字符串附加到"number"的答案字符串次。
步骤 11 − 返回"答案"字符串。
示例
#include <bits/stdc++.h>
using namespace std;
string decodeTheString(string alpha) {
string answer = "";
// 迭代字符串字符
for (int i = 0; i < alpha.length(); i++) {
// 除了右括号之外的所有其他字符
if (alpha[i] != ']') {
answer.push_back(alpha[i]);
} else {
// 提取对中的子字符串
string temp_str = "";
// 继续弹出字符，直到找到 '['。
while (!answer.empty() && answer.back() != '[') {
temp_str.push_back(answer.back());
answer.pop_back();
}
// 通过反转字符串获取原始字符串
reverse(temp_str.begin(), temp_str.end());
// 删除左括号
answer.pop_back();
// 获取 '[' 字符前的整数值
string number = "";
// 获取左括号前的数字
while (!answer.empty() && answer.back() >= '0' && answer.back() <= '9') {
number.push_back(answer.back());
answer.pop_back();
}
// 反转数字字符串
reverse(number.begin(), number.end());
// 将字符串转换为整数
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 << "解码后的结果字符串为 - " << decryptTheString(str) << endl;
return 0;
}
输出
解码后的结果字符串为 − ddcnncnncnn
时间复杂度− O(N^2)，因为我们遍历字符串并在循环内使用 reverse() 方法。
空间复杂度− O(N) 来存储数字和临时字符串。
