LeetCode 75 Level 1 - Day 14 Stack

844. Backspace String Compare

• 題目連結
• 難易度：Easy

題目敘述

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.
Note that after backspacing an empty text, the text will continue empty.

預設函數

bool backspaceCompare(char * s, char * t){

}

題目限制

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

解題過程及程式碼

本題輸入給2個字串 s 和 t，兩個字串都是由小寫字母和 '#' 這個字元組成，題目要判斷 s 和 t 在經過處理後是否相同？這個處理就是遇到 '#' 時要像按了鍵盤的Backspace鍵一樣，將 '#' 前的字母刪除變成新的字串。

• 例如s = "ab#c", t = "ad#c"，處理後 s 和 t 都是**"ac"**。
• 例如s = "ab##", t = "c#d#"，處理後 s 和 t 都是空的**""** (有幾個 '#' 就刪幾個字母)。

本題想法是將 s[i] 字元依次丟入Stack (叫它stack_s)中，如果遇到了 '#' 而且stack_s它不空時取出 '#' 之前最後丟入的字母，再用相同方法將 t[i] 丟至stack_t中，最後將stack_s與stack_t做比較：

• 如果兩個Stack都是空的 -> 可直接判斷兩者相同 (true)。
• 如果兩個Stack頭元素不同 -> 可直接判斷兩者不同 (false)，
• 如果不是上面兩個判斷成立 -> 再一個一個比較元素是否相同。

寫解題程式前先來複習C語言中Stack的用法：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define MAX_STACK_SIZE 100

typedef struct {
    int key;
} element;

void push(element);
element pop(void);
int isEmpty(void);

element stack[MAX_STACK_SIZE];
int top;

int main() {
    element item1, item2;

    top = -1;
    item1.key = 7;
    item2.key = 9;
    push(item1);
    push(item2);
    printf ("pop: %d\n", pop().key);
    printf ("pop: %d\n", pop().key);
    return 0;
}

/* 將元素丟入Stack裡 */
void push(element item) {
    stack[++top] = item;
}

/* 將元素由Stack裡取出 */
element pop(void) {
    return stack[top--];
}

/* 判斷Stack是否空 */
int isEmpty(void) {
    if (top == -1) return 1;
    else return 0;
}

程式碼上傳

#define MAX_STACK_SIZE 200

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

char stack_s[MAX_STACK_SIZE];
char stack_t[MAX_STACK_SIZE];
int top_s;
int top_t;


bool backspaceCompare(char * s, char * t){
    int i;

    top_s = -1;
    top_t = -1;
    
    /* 處理字串s */
    i = 0;    
    while (s[i] != '\0') {
        if (s[i] != 35) {
            push(stack_s, &top_s, s[i]);
        } else if (!isEmpty(&top_s) && (s[i] == 35)) {
            pop(stack_s, &top_s);
        }
        i++;
    }

    /* 處理字串t */
    i = 0;
    while (t[i] != '\0') {
        if (t[i] != 35) {
            push(stack_t, &top_t, t[i]);
        } else if (!isEmpty(&top_t) && (t[i] == 35)) {
            pop(stack_t, &top_t);
        }
        i++;
    }

    /* 比較stack_s和stack_t */
    if ((top_s == -1) && (top_t == -1)) {
        return true;
    } else if (top_s != top_t) {
        return false;
    } else {
        i = 0;
        while (top_s >= 0) {
            if (pop(stack_s, &top_s) != pop(stack_t, &top_t))
                return false;
        }
        return true;
    }
}

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

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

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

今天走到了30天的90%了，謝謝大家看完。