注册企业网站,广州网站导航,网站模板带手机站,校园网站建设公司leetcode原题链接: 字符串解码
题目描述 给定一个经过编码的字符串#xff0c;返回它解码后的字符串。
编码规则为: k[encoded_string]#xff0c;表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的#xff1b;输… leetcode原题链接: 字符串解码
题目描述 给定一个经过编码的字符串返回它解码后的字符串。
编码规则为: k[encoded_string]表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输入。
示例 1
输入s 3[a]2[bc]
输出aaabcbc示例 2
输入s 3[a2[c]]
输出accaccacc示例 3
输入s 2[abc]3[cd]ef
输出abcabccdcdcdef示例 4
输入s abc3[cd]xyz
输出abccdcdcdxyz提示
1 s.length 30s 由小写英文字母、数字和方括号 [] 组成s 保证是一个 有效 的输入。s 中所有整数的取值范围为 [1, 300]
解题方法采用栈。遍历字符串用字符串变量result保存最终的结果遍历过程中用栈保存当前需要扩展的次数和待扩展字符串的首字母在result中的位置 。具体如下
1遇到数字计算下需要扩展的次数
2遇到字母则将字母追加到结果变量result中
3遇到[, 则将扩展的次数count,扩展首字母在扩展遍历result中的位置 保存在栈中,同时重置count的值为0
4遇到], 则开始扩展字符, 扩展的次数和扩展的字符都可以通过栈中的信息拿到。扩展完后要将栈顶元素弹出。因为可能会有嵌套扩展的情况。如3[a2[c]]
C代码
#include iostream
#include stack
#include string
#include utility // std::pair
#include cctype //isdigit(), isalpha()
/*
* 解题方法
* 扫描字符串
* 1. 遇到数字计算下需要扩展的次数
* 2. 遇到字母则将字母追加到结果变量result中
* 3. 遇到[, 则将扩展的次数count,扩展首字母在扩展遍历result中的位置保存在栈中,同时重制count的值为0
* 4. 遇到], 则开始扩展字符, 扩展的次数和扩展的字符都可以通过栈中的信息拿到,扩展完后要将栈顶元素弹出。因为可能
* 会有嵌套扩展的情况。
*/
class Solution {
public:string decodeString(std::string s) {int n s.size();std::stackstd::pairint, int st; //保存本次扩展的次数count, 扩展字符串在result的开始位置std::string result;int count 0;for (int i 0; i n; i) {if (isdigit(s[i])) { //数字count 10 * count (s[i] - 0);} else if (s[i] [) { //遇到左括号[ 则保存count和循环长度st.push({count, result.size()});count 0;} else if (isalpha(s[i])) { //遇到字母追加到result中result s[i];} else if (s[i] ]) { //遇到右括号] 则开始扩展int count st.top().first;int start_pos st.top().second;// abcd start_pos0, len4int len result.size() - start_pos;std::string extend_str result.substr(start_pos, len); //注意这里只能扩展count-1次因为result上已经记录过一次了for (int k 0; k count - 1; k) {result extend_str;}st.pop(); //每扩展完都需要弹出栈顶元素,考虑这种情况: 3[a2[c]] st: (3,0), (2, 1)}}return result;}
};
