yoruru的努力日記

1209. Remove All Adjacent Duplicates in String II

You are given a string s and an integer k, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them, causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed that the answer is unique.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

SOL：

這一題的解法是把字串s一個個放到stack，因為題目是要連續的字母，所以我們同時會有一個count，來記錄字母的累加情況。

思路我是參考這篇：LeetCode 1209. Remove All Adjacent Duplicates in String II 中文解释 Chinese Version

char * removeDuplicates(char * s, int k){
    int len = strlen(s); //not containing '\0'
    char *stack = (char *)malloc(sizeof(char)*(len+1)); //len+'\0'
    int *count = (int *)malloc(sizeof(int)*len);
    int top = -1;
    for(int i = 0; i < len; i++){
        if(top>=0 && stack[top]==s[i]){
            ++top;
            stack[top] = s[i];
            count[top] = count[top-1]+1;
        }
        else{
            ++top;
            stack[top] = s[i];
            count[top] = 1;
        }
        if(count[top]==k){ //pop top k if k duplicate adjacent letters
            top -= k;
        }
    }
    stack[top+1]='\0'; // add '\0' for copying string
    char *result=strdup(stack);
    free(stack);
    free(count);
    return result;
}

需要注意的是，因為我們最後要用 strdup 來複製在stack裡的字元所形成的字串，而 char *stack 並沒有存字串結束字元 '\0'，所以我們必須指定 stack[top+1]='\0' 才能用strdup複製字串。但因為 len = strlen(s) 不包含結束字元，也就是當第一個例子中 s="abcd"，len=4。 倘若一開始宣告 stack 只有 len 這個大小的話，因為沒有任何相鄰的字母，所以stack會放入字串s中的所有字元，也就是index: 0-3都會有值，當我們為了複製字串stack而在 top+1 加入 '\0' 時，會造成 out of index ( heap-buffer-overflow )。

為了避免此問題，我在宣告stack大小時會多加一個char。

char *stack = (char *)malloc(sizeof(char)*(len+1)); //len+'\0'

ps. 這可是chatgpt也會犯的錯呢XD

自從發現chatgpt也會寫錯之後，我現在都要先run一下它的程式碼確定無誤再認真看，我真的不想幫AI debug 哈