极客笔记C++ 递归解码字符串编码为次数后跟子字符串
在这个问题中，我们需要通过反复添加总计次数来解码给定的字符串。
我们可以有三种不同的方法来解决这个问题，可以使用两个栈或一个栈来解决问题。另外，我们还可以不使用这两个栈来解决问题。
问题陈述 - 我们给出了一个字符串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 − 将‘num’初始化为0，以存储当前字符是否为数字。
步骤3.1 − 如果第p个索引处的字符是一个数字字符，则在获取到一个字母字符或括号之前遍历字符串。在循环中，将‘num’的先前值乘以10，并将当前数字加到其中。
步骤3.2 − 将‘p’的值增加1。
步骤3.3 − 将数字的值推入‘instSt’栈中。
步骤4 − 如果第pth索引处的字符是闭括号，则按以下步骤进行操作。
步骤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 - 如果“answer”字符串顶部包含数字，则使用数字构成一个整数，并将其存储在number变量中。
步骤8 - 反转数字字符串。
步骤9 - 使用stoi()方法将字符串转换为数字。
步骤10 - 将temp_Str字符串附加到answer字符串中的“number”次。
步骤11 - 返回“answer”字符串。
示例
#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)，用于存储数字和临时字符串。