LeetCode 75 Level 1 - Day 14 Stack

394. Decode String

• 題目連結
• 難易度：Medium

題目敘述

Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like or .
The test cases are generated so that the length of the output will never exceed .

預設函數

int numIslands(char** grid, int gridSize, int* gridColSize){

}

題目限制

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[]'.
• s is guaranteed to be a valid input.
• All the integers in s are in the range [1, 300].

解題過程及程式碼

本題希望我們做出一個字串的解碼程式，題目給一個字串例如 "3[a]2[bc]"，要將 "[ ]" 內部的內容重複輸出數次，重複次數就是 "[ ]" 前面的數字，於 "3[a]2[bc]" 經過處理後就是 "aaabcbc"。

最初想法是把 s[i] 依序處理，遇到數字就push(s[i])到stack2，遇到 '[' 就push()後面準備等 ']'，遇到字母就push(s[i])到stack1，最後遇到 ']' 就進行處理，由stack2中計算應該重複幾次，由stack1中計算要重複字元的範圍[i~j]進行計算。

• 程式碼嘗試 (無法通過測試)

#define MAX_STACK_SIZE 200

void push(char *, int *, char);
char pop(char *, int *);
int isEmpty(int *);
char peek(char *, int);

char stack1[MAX_STACK_SIZE];
char stack2[MAX_STACK_SIZE];
int top1;
int top2;
char *ptr;

char * decodeString(char * s){
    int i, j, k, bracket, repeat, power, pos;

    top1 = -1;
    top2 = -1;
    i = 0;
    while (s[i] != '\0') {
        // 1-9
        if ((s[i] >= 48) && (s[i] <= 57)) {
            push(stack2, &top2, s[i]#include <string.h>);
        // '['
        } else if (s[i] == 91) {
            push(stack1, &top1, s[i]);
            push(stack2, &top2, s[i]);
        // a-z
        } else if ((s[i] >= 97) && (s[i] <= 122)) {
            push(stack1, &top1, s[i]);
        // ']'
        } else if (s[i] == 93) {
            pop(stack2, &top2);
            repeat = 0;
            power = 0;
            /* 找出重複次數 */
            while (top2 != -1) {
                if ((peek(stack2, top2) >= 48) && (peek(stack2, top2) <= 57)) {
                    repeat += (pop(stack2, &top2) - 48) * pow(10, power);
                    power++;
                }
            }
            /* 找出從top到最近的'['位置 -> 確定重複字串的範圍 */
            pos = 0;
            j = top1;
            while (peek(stack1, j) != 91) {
                pos = j;
                j--;
            }

            /* 利用重複次數及重複字串範圍進行重複 */
            k = 0;
            int num = top1;
            while (k < repeat-1) {
                for (int n=pos; n<=num; n++) {
                    push(stack1, &top1, peek(stack1, n));
                    /* 問題在push()完後stack1裡面還有'['又會影響到下一次的計算 */
                }
                k++;
            }
        }
        i++;
    }

    ptr = (char *)malloc(MAX_STACK_SIZE * sizeof(char));

    i = 0;
    while (i <= top1) {
        ptr[i] = peek(stack1, i);
        i++;
    }
    ptr[i] = '\0';

    return ptr;
}

void push(char *s, int *top, char item) {
    s[++(*top)] = item;
}

char pop(char *s, int *top) {
    return s[(*top)--];
}

char peek(char *s, int top) {
    return s[top];
}

int isEmpty(int *top) {
    if (*top == -1) return 1;
    else return 0;
}

參考他人的作法後，發現應該放入stack的不是char，應該把 '[' 之前的數字先解析為整數(int)後放入stack1 (元素是整數)，把 '[' 和 ']' 中間的字串放入另一個stack2，為此stack2要放的元素是字串。

• [LeetCode] 394. Decode String 解码字符串
• 程式碼上傳

#include <string.h>

#define MAX_STACK_SIZE 200
#define MAX_STRING_SIZE 5000

typedef struct {
    char str[MAX_STRING_SIZE];
    int num;
} element;

void push(element, element *, int *);
element pop(element *, int *);
int isEmpty(int *);
element peek(element *, int *);

element stack1[MAX_STACK_SIZE];
element stack2[MAX_STACK_SIZE];
int top1;
int top2;
char *ptr;
char str_temp[MAX_STRING_SIZE];

char * decodeString(char * s){
    int i, repeat, number;
    char str_strcat[100];
    char char_temp[4];
    element input;

    top1 = -1;
    top2 = -1;
    repeat = 0;
    strcpy(str_temp, "");
    strcpy(str_strcat, "");
    strcpy(char_temp, "");

    i = 0;
    while (s[i] != '\0') {
        /* 遇到 1-9 */
        if ((s[i] >= '0') && (s[i] <= '9')) {
            repeat = (10 * repeat) + (s[i] - '0');
        /* 遇到 '[' */
        /* 數字結束了，要準備收字串 */
        } else if (s[i] == '[') {
            /* repeat的數字放入Stack裡 */
            input.num = repeat;
            push(input, stack2, &top2);  // stack2[i]放數字
            repeat = 0;

            /* 字串放入Stack裡 */
            strcpy(input.str, "");
            strcpy(input.str, str_temp);
            push(input, stack1, &top1);  // stack1[i]放字串
            strcpy(str_temp, "");
        /* 遇到 a-z */
        } else if ((s[i] >= 'a') && (s[i] <= 'z')) {
            strcpy(char_temp, "");
            char_temp[0] = s[i];
            char_temp[1] = '\0';
            strcat(str_temp, char_temp);
        /* 遇到 ']' */
        } else {
            /* 從數字的Stack取出頭元素 */
            number = pop(stack2, &top2).num;

            /* 將字串Stack的頭元素重複 */
            for (int j=0; j<(number); j++) {
                strcat(stack1[top1].str, str_temp);
            }
            /* 取出頭元素存入字串str_temp */
            strcpy(str_temp, "");
            strcpy(str_temp, stack1[top1].str);
            pop(stack1, &top1);
        }
        i++;
    }

    return str_temp;
}

void push(element item, element *s, int *t) {
    s[++(*t)] = item;
}

element pop(element *s, int *t) {
    return s[(*t)--];
}

element peek(element *s, int *t) {
    return s[*t];
}

int isEmpty(int *t) {
    if (*t == -1) return 1;
    else return 0;
}

今天就到這裡，謝謝大家。