1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)

給出由小寫(xiě)字母組成的字符串 S，重復(fù)項(xiàng)刪除操作會(huì)選擇兩個(gè)相鄰且相同的字母，并刪除它們。
在 S 上反復(fù)執(zhí)行重復(fù)項(xiàng)刪除操作，直到無(wú)法繼續(xù)刪除。
在完成所有重復(fù)項(xiàng)刪除操作后返回最終的字符串。答案保證唯一。
示例：

輸入："abbaca"
輸出："ca"
解釋?zhuān)?例如，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同，這是此時(shí)唯一可以執(zhí)行刪除操作的重復(fù)項(xiàng)。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復(fù)項(xiàng)刪除操作，所以最后的字符串為 "ca"。

題解

使用棧，遍歷該字符串，如果當(dāng)前字符和棧頂字符相同，我們就將其消去，否則就將其入棧。

    public String removeDuplicates(String S) {
        if (S == null || S.length() < 1) {
            return null;
        }
        Deque<Character> stack = new ArrayDeque<>();
        char[] chars = S.toCharArray();
        int i = 0;
        while (i < chars.length) {
            char cur = chars[i++];
            if (!stack.isEmpty() && stack.peek() == cur) {
                stack.pop();
                continue;
            }
            stack.push(cur);
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

分享一個(gè)原地的算法

    public String removeDuplicates(String S) {
        char[] s = S.toCharArray();
        int top = -1;
        for (int i = 0; i < S.length(); i++) {
            if (top == -1 || s[top] != s[i]) {
                s[++top] = s[i];
            } else {
                top--;
            }
        }
        return String.valueOf(s, 0, top + 1);
    }