394. 字符串解码

地址:

力扣394. 字符串解码https://leetcode-cn.com/problems/decode-string/

题目:

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: 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"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

观察给定字符串,其展开顺序是由 右->左,一个展开单元为  

数字 + [ 字母 ]

展开完成后又与左边未展开部分结合为新的字符串,再继续重复动作,直至完全展开

这种操作就很典型的 堆 ,先进后出,左边的最后展开。

我们考虑用堆来实现这个展开过程:

1. 字符依次入堆

2. 遇见 右括号 ] 停止入堆,意味着堆里面已经存放有对应的 左括号 [

3. 将堆里面依次出堆,直到遇见 非数字。这里要特别处理下,因为数字可能不是单位数,所以要将数字合并成实际数字

4. 堆是反向的顺序,所以这里我们又可以借由另一个堆B,将 堆A 的出堆字符 入堆B,那么堆B再出堆就是正序了

5. 堆B里面存放类似 12[ab ,我们就需要构建 abab...ab(12个ab)的字符串

6. 构建完的字符串需要重新与原有字符串组合,即我们要将字符串入堆 A

7. 堆A 的大小需要重新扩展,否则没有办法装入

8. 最后这样循环完成后,堆A存放的就是反序字符串,我们再做一次反序就得到结果

示例:

依序入堆,直到遇见右括号 ]

394. 字符串解码

将 堆A 入 堆B,达到反序,堆B操作字符串,构建出重复的字符串

394. 字符串解码

将构建好的字符串重新入堆A

394. 字符串解码

继续原本字符串的后续字符处理,依次入堆A

394. 字符串解码 

又一次处理右括号情况

394. 字符串解码

再一次将构建好的字符串入堆A,整个字符串全部处理完成,堆A存放反序结果,再一次反序即可

394. 字符串解码

方法一、堆操作

由于 C 没有提供现成的 堆,我们需要自行完成 堆的部分,然后才开始本题的逻辑部分

typedef struct {
    char *stk;
    int stkSize;
    int stkCapacity;
} MyStack;

MyStack *myStackCreate(int capacity)
{
    MyStack *stack = (MyStack *)malloc(sizeof(MyStack));

    stack->stk = (char *)malloc(sizeof(char) * capacity);
    stack->stkSize = 0;
    stack->stkCapacity = capacity;

    return stack;
}

void myStackFree(MyStack *stack)
{
    if(stack)
    {
        free(stack->stk);
        free(stack);
    }
}

int myStackEmpty(MyStack *stack) {
    return stack->stkSize == 0;
}

void myStackPush(MyStack *stack, char x)
{
    stack->stk[stack->stkSize++] = x;
}

void myStackPop(MyStack *stack)
{
    stack->stkSize--;
}

int myStackTop(MyStack *stack)
{
    return stack->stk[stack->stkSize - 1];
}

构建重复字符串过程

char * repeatStr(MyStack *stack)
{
	int i,j;
	int c;
	int num = 0;
	int numDone = -1;
	int stkLen = stack->stkSize;
	int comStrLen = 0;
	int repStrLen = 0;
	MyStack *newStk = myStackCreate(stkLen);
	char *comStr = (char *)malloc(sizeof(char) * stkLen);
	char *repStr = NULL;
		
	// to revert string
	while( ! myStackEmpty(stack) )
	{
		c = myStackTop(stack);
		myStackPop(stack);
		
		if(isdigit(c))
			numDone = 0;
		else if(numDone == 0)
		{
			numDone = 1;
			myStackPush(stack, c);
			break;
		}
				
		myStackPush(newStk, c);	
	}
		
	// now the reverted string store in newStk
	printf("repeatStr..newStk size=%d\n", newStk->stkSize);
	i=0;
	while( ! myStackEmpty(newStk) )
	{
		c = myStackTop(newStk);
		myStackPop(newStk);
		printf("repeatStr..3.pop c=%c\n", c);
		
		if(isdigit(c))
		{
			num *= 10;
			num += c - 48; // char to int	
			printf("num=%d\n", num);
		}				
		else if( c == '[')
		{
			continue;
		}
		else // combine string
		{
			comStr[i++] = c;
		}
	}
	comStr[i] = '\0';
	
	printf("repeatStr..num=%d\n", num);
	printf("repeatStr..comStr=%s\n", comStr);
	
	// repeated string
	comStrLen = strlen(comStr); 
	repStrLen = (num * comStrLen);
	repStr = (char *)malloc(sizeof(char) * repStrLen + 1);
	
	j = 0;
	while(num--)
	{
		sprintf(repStr+j, "%s", comStr);
		j += comStrLen;
	}
	
	free(comStr);
	myStackFree(newStk);
	
	return repStr;
}

扫描原始字符串,入堆操作或进行重复字符串处理

char * decodeString(char * s)
{
	int i = 0, j = 0;
	int reallocLen = 0;
	char c;
	char *p = s;
	char *q = NULL;	// to point to repeated string
	char *repStr = NULL;
	char *decStr = NULL;
	int repStrLen = 0;
	int decStrLen = 0;
	MyStack *stk = myStackCreate(strlen(s));
	MyStack *tmpStk = NULL;
	
	while(p[i])
	{
		if( p[i] == ']')
		{
			repStr = repeatStr(stk);
			repStrLen = strlen(repStr);

			// push repeated string to stack
			reallocLen = stk->stkCapacity + repStrLen;
			stk->stk = (char *)realloc(stk->stk, sizeof(char) * reallocLen);
			stk->stkCapacity = reallocLen;
			
			q = repStr;
			j = 0;
			while(q[j])
			{
				myStackPush(stk, q[j]);
				j++;
			}
			
			free(repStr);
		}
		else	
		{
			printf("push p[%d]=%c\n", i, p[i]);
			myStackPush(stk, p[i]);
		}
		
		i++;
	}
	
	decStrLen = stk->stkSize; 
	decStr = (char *)malloc(sizeof(char) * stk->stkSize + 1);
	tmpStk = myStackCreate(stk->stkSize);
	
	// revert stk
	while( ! myStackEmpty(stk) )
	{
		c = myStackTop(stk);
		myStackPop(stk);
		
		myStackPush(tmpStk, c);
	}
	
	i = 0;
	while( ! myStackEmpty(tmpStk) )
	{
		decStr[i++] = myStackTop(tmpStk);
		myStackPop(tmpStk);
	}
	decStr[i] = '\0';
	
	myStackFree(stk);
	myStackFree(tmpStk);
	
	return decStr;
}

查看更多刷题笔记

上一篇:C++STL标准库学习笔记(十二)容器适配器


下一篇:js—深度优先遍历(DFS)和广度优先遍历(BFS)