题目描述
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
样例
样例输入 #1
s = "3[a]2[bc]"
样例输出 #1
"aaabcbc"
样例输入 #2
s = "3[a2[c]]"
样例输出 #2
"accaccacc"
样例输入 #3
s = "2[abc]3[cd]ef"
样例输出 #3
"abcabccdcdcdef"
样例输入 #4
s = "abc3[cd]xyz"
样例输出 #4
"abccdcdcdxyz"
提示
- 1 <= s.length <= 30
- s 由小写英文字母、数字和方括号 '[]' 组成
- s 保证是一个 有效 的输入。
- s 中所有整数的取值范围为
[1, 300]
题解
思路一：递归
1.将字符串拆解成倍数和字符
2.将字符复制
3.字符内若任有'[]'，则递归重复上述操作
- 注意：函数返回的字符串要经过动态分配
C代码
struct take_apart { //定义结构体，方便函数decode_square_brackets(char* s)同时返回拆解后的倍数和字符
int number; //用于存储方括号前的倍数
char string[35]; //用于存储方括号内的字符串
};
struct take_apart decode_square_brackets(char* s) //输入3[a2[c]],拆解成3 & a[2[c]]
{
struct take_apart ret;
sscanf(s, "%d[%s", &ret.number, ret.string); //拆解
ret.string[strlen(ret.string) - 1] = '\0';//把最后的“]”换成空字符
return ret;
}
char* decode(char s[], int begin, int end) {
int ptr_ret = 0;//返回数组的操作位
char* ret = (char*)malloc(sizeof(char) * 1800); //用于存储解码后的字符串
while (begin <= end)//遍历全数组
{
if (isdigit(s[begin])) //如果出现数字，如"3[a2[c]]"
{
char square_brackets[35]; //需要拆解的字符串
int ptr_square_brackets = 0;
int count_square_brackets = 0; //标记左方括号的出现次数，以保证对应的左右方括号一一配对
while (1) //将s[]中需要拆解的字符串拷贝到square_brackets[]中，便于用sscanf()处理
{
if (s[begin] == '[')
count_square_brackets++; //出现左方括号，累加
if (s[begin] == ']')
count_square_brackets--; //出现右方括号，递减
square_brackets[ptr_square_brackets++] = s[begin++]; //将需要拆解字符串拷贝到square_brackets[]数组中
if (count_square_brackets == 0 && square_brackets[ptr_square_brackets - 1] == ']') //如果左右方括号一一对应，并且读取到']'时
break; //拷贝结束，跳出循环
}
square_brackets[ptr_square_brackets] = '\0';//在字符串末尾添加空字符
struct take_apart ret_square_brackets = decode_square_brackets(square_brackets);//将 倍数 与 方括号内的字符串 拆解开，分别存储
int num = ret_square_brackets.number;//倍数
char next_ret[300];//方括号内的字符串
sprintf(next_ret, "%s", decode(ret_square_brackets.string, 0, strlen(ret_square_brackets.string) - 1)); //将方括号内的字符串继续解码，实现递归
int len = strlen(next_ret);
for (int i = 0; i < num; i++) //将next_ret[]中的字符串复制num次
{
for (int j = 0; j < len; j++)
ret[ptr_ret++] = next_ret[j];
}
}
while (isalpha(s[begin])) //处理方括号外的单独字母
{
ret[ptr_ret++] = s[begin++];
}
}
ret[ptr_ret] = '\0'; //补足空字符
return ret;
}
char* decodeString(char* s) {
return decode(s, 0, strlen(s) - 1);
}
思路二：数组栈模拟
1.像开花一样将方括号内的字符串从内到外层层展开
2.用ptr_alpha标记处理到的位置，不用担心展开时出现“覆盖到相邻位置”的情况
C代码
char* decodeString(char* s) {//拆解字符串，例如："3[a]2[bc]"
char* stack_num = (char*)malloc(sizeof(char) * 20);//用于存储数字位，如："3[2["
char* stack_alpha = (char*)malloc(sizeof(char) * 1800);//用于存储字符位，如："[a[bc"
int len = strlen(s);
int ptr_num = 0, ptr_alpha = 0;
for (int i = 0; i < len; i++) {
char temp = s[i];//拷贝s[i]至temp，减少数组寻址时间
if (temp == '[') {//对于'['，同时存储
stack_num[ptr_num++] = '[';
stack_alpha[ptr_alpha++] = '[';
}
else if (isdigit(temp)) {//将数字存放至stack_num[]
stack_num[ptr_num++] = temp;
}
else if (isalpha(temp)) {//将字母存放至stack_alpha[]
stack_alpha[ptr_alpha++] = temp;
}
else if (temp == ']') {//读取到']'，开始处理
int number = 0;
int ten_times = 1;
ptr_num = ptr_num - 2;
while (ptr_num >= 0 && stack_num[ptr_num] != '[') {//将倍数转换为十进制，并存放到number
number += (stack_num[ptr_num] - '0') * ten_times;
ten_times *= 10;
ptr_num--;
}
ptr_num++;//将ptr_num重新对准'['位，便于处理
ptr_alpha--;//将ptr_alpha也重新对准'['位，便于处理
char copy[300];//存放用于翻倍的字符串
int ptr_copy = 300;
while (stack_alpha[ptr_alpha] != '[') {
copy[--ptr_copy] = stack_alpha[ptr_alpha--];//逆序存储，便于正序输出
}
while (number--) {//将copy[]中的字符串，翻倍number次，并存放到stack_alpha中
for (int j = ptr_copy; j < 300; j++) {
stack_alpha[ptr_alpha++] = copy[j];
}
}
}
}
stack_alpha[ptr_alpha] = '\0';
return stack_alpha;
}