删除字符串中的所有相邻重复字符

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，1047. Remove All Adjacent Duplicates In String

先看题目描述

614eG8.png

大意就是给定一个字符串 S，删除重复项的操作就是选取两个相邻且相等的字母删除，重复进行删除重复项操作直至不能再删除，返回最后的字符串

算法和思路

栈

使用栈来存储结果字符串即可，遍历字符串 S，当栈顶字符与当前遍历字符相等时，则删除栈顶字符；否则，将当前遍历字符添加至栈顶。最后栈中字符构成字符串即可

算法源码

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public String removeDuplicates(String S) {
        StringBuilder stack = new StringBuilder();
        int top = -1;
        char[] cs = S.toCharArray();
        for (char c : cs) {
            if (top >= 0 && c == stack.charAt(top)) {
                stack.deleteCharAt(top);
                top--;
            } else {
                stack.append(c);
                top++;
            }
        }
        return stack.toString();
    }
}

下面是自己一开始实现的用一个指针的代码，效率比栈差一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String removeDuplicates(String S) {
        StringBuilder sb = new StringBuilder(S);
        int index = 1;
        while (index < sb.length()) {
            if (index > 0 && sb.charAt(index - 1) == sb.charAt(index)) {
                sb.delete(index - 1, index + 1);
                index -= 2;
            }
            index++;
        }
        return sb.toString();
    }
}