数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究递归解码以计数后跟子字符串编码的字符串
在这个问题中，我们需要通过重复添加总计数次数来解码给定的字符串。
我们可以采用三种不同的方法来解决这个问题，我们可以使用两个栈或一个栈来解决这个问题。此外，我们也可以不用两个栈来解决这个问题。
问题陈述 - 我们得到一个包含开闭括号、字母和数字字符的字符串 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 - 如果第 p 个索引处的字符是右括号，请按照以下步骤操作。
步骤 4.1 - 使用空字符串初始化 ‘temp_str’。之后，如果 ‘instSt’ 不为空，则从栈中弹出顶部整数。
步骤 4.2 - 现在，使用循环直到我们得到左括号或栈从 ‘strSt’ 栈变空。另外，将字符附加到 ‘temp_str’。
步骤 4.3 - 如果我们由于 ‘[‘ 而停止弹出字符，则将其删除。
步骤 4.4 - 接下来，我们需要将 ‘temp_Str’ 附加到 ‘answer’ 字符串中 ‘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)，用于存储数字和临时字符串。
浏览量 232
