394.字符串解码

​394.字符串解码

​394.字符串解码

题目分析

对这个题目的需求进行分析(需求分析来自Leetcode用户名为凛冬^[1])
我只是稍微修改了具体内容(官方视频讲解^[2])

1. 采用栈的方式解题(解题方式有很多)
2. 遍历给定的字符串，将不是']'的字符入栈
3. 遇到"]",开始出栈，直到'['
4. 在将'['前的数字出栈(因为题目意思是重复k次，1次不算重复，说明k大于等于2，也就表示'['前一定有数字)
5. 因为出栈的字符串是翻转过的，因此翻转后，将字符串重新压入栈，重复k次
6. 继续遍历直到最后

代码实现

/*来自Leetcode用户凛冬*/
char * decodeString(char * s){
int len = (int)strlen(s);
    int stackSize = 50;
    char* stack = (char*)malloc(stackSize * sizeof(char));
    int top = -1;
​
    for (int i=0; i<len; i++) {
        char c = s[i];
        if (c != ']') {//如果字符不是]则一直入栈
            if (top==stackSize-1) {//如果此时栈满了 就扩容
                stack = realloc(stack, (stackSize += 50) * sizeof(char));
            }
            stack[++top] = c;
        } else {
            //创建临时数组 存放要复制的字符
            int tempSize = 10;
            char* tempStack = (char*)malloc(tempSize * sizeof(char));
            int tempTop = -1;
            //出栈 得到到要复制的字符串
            while (stack[top] != '[') {
                if (tempTop==tempSize-1) {
                    tempStack = realloc(tempStack, (tempSize += 10)*sizeof(char));
                }
                //栈顶元素存入临时数组
                tempStack[++tempTop] = stack[top];
                //stack 出栈
                top--;
            }
            //翻转字符串，将字符串翻正
            char *cpyStr = (char*)malloc((tempTop+2)*sizeof(char));
            for (int i=tempTop; i>=0; i--) {
                cpyStr[tempTop-i] = tempStack[i];
            }
            cpyStr[++tempTop] = '\0';
​
            //'['出栈
            top--;
​
            //取出需要复制的数量
            int cpyNum = 0;
            int j = 0;
            while (top>=0 && stack[top]>='0' && stack[top]<='9') {
                cpyNum += (stack[top]-'0')*pow(10, j); //防止有2位数甚至3位数
                top--;
                j++;
            }
​
            //复制的字符重新入栈
            for (int i=0; i<cpyNum; i++) {
                for (int j=0; j<strlen(cpyStr); j++) {
                    if (top==stackSize-1) {//如果此时栈满了 就扩容
                        stack = realloc(stack, (stackSize += 50) * sizeof(char));
                    }
                    stack[++top] = cpyStr[j];
                }
            }
​
            free(tempStack);
        }
    }
​
    char* result = realloc(stack, (top + 2) * sizeof(char));
    result[++top] = '\0';
​
    return result;
}

复杂度分析

空间复杂度: O(S)，因为需要栈的长度不会超过S的长度。
时间复杂度: O(S)
S为解码后的字符串

思考反思

代码实现有很多方法，递归也可以实现。但是对于题目的解读十分重要，需要对题目的需求进行分析以及归纳，需要采用伪代码的形式，模拟过程，然后归纳问题。

递归的解题方式就是需要找到子问题，也就是找到代码中的共同点。

References

[1] 需求分析来自Leetcode用户名为凛冬: https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-lin-dong-n/
[2] 官方视频讲解: https://leetcode-cn.com/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/