题目

文本

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1 <= S.length <= 20000
S 仅由小写英文字母组成。

来源：力扣（LeetCode）

模板

char * removeDuplicates(char * S){

}

解答

分析

本题可以使用栈的方法来解决。
对于题意理解出现多组相邻重复项并不会影响最终的处理结果，所已采取从左到右的消除顺序。
而因为消除当前的相邻重复可能会导致出现新的相邻重复需要消除的情况，所以这种情况之下是可以使用栈来解决的。
首先初始化一个简单的栈来进行后面的对比操作。（同时得到字符串长度为后面循环做界限，以及返回大小的初始化）

    int n = strlen(S);
    char* stk = malloc(sizeof(char) * (n + 1));//获取n+1个内存大小，为了防止没有重复消除的元素
    int retSize = 0;

由于可能会没有重复消除的元素所以最后栈stk的最后元素（栈顶）用'/0’

    stk[retSize] = '\0';

按顺序入栈，如果有重复元素就消除，同时栈顶元素也会消除掉

    for (int i = 0; i < n; i++) {
        if (retSize > 0 && stk[retSize - 1] == S[i]) {
            retSize--;
        } else {
            stk[retSize++] = S[i];
        }
    }

完整源码

char* removeDuplicates(char* S) {
    int n = strlen(S);
    char* stk = malloc(sizeof(char) * (n + 1));
    int retSize = 0;
    for (int i = 0; i < n; i++) {
        if (retSize > 0 && stk[retSize - 1] == S[i]) {
            retSize--;
        } else {
            stk[retSize++] = S[i];
        }
    }
    stk[retSize] = '\0';
    return stk;
}

运行结果

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。