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

Q

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

 

示例：

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

A

递归

分解问题

1.单次删除重复项操作

去除第一个遇到的重复项操作

String str = "abbaca";
char[] chars = str.toCharArray();
//分解步骤
char[] temp = new char[chars.length-2];
for (int i = 0; i <chars.length-1 ; i++) {
    if(chars[i]==chars[i+1]){
        for (int j = i; j < chars.length-2 ; j++) {
            chars[j] = chars[j+2];
            System.arraycopy(chars,0,temp,0,chars.length-2);
        }
    }
}

2.递归重复操作

设置baseCase，进行递归调用

public static char[] deleteRepeat(char[] chars){
        //base case 跳出递归的条件，数组全删完了 或者只剩下一位
        if(chars.length == 0 || chars.length == 1){
            return chars;
        }
        //存放删除一组重复元素后的数组
        char[] temp = new char[chars.length-2];
        //循环当前参数数组
        for (int i = 0; i <chars.length-1; i++) {
            //出现重复元素
            if(chars[i]==chars[i+1]){
                //删除重复元素
                for (int j = i; j < chars.length-2 ; j++) {
                    chars[j] = chars[j+2];
                }
                System.arraycopy(chars,0,temp,0,chars.length-2);
                //递归判断剩下的元素是否存在重复元素并继续删除
                return deleteRepeat(temp);
            }
        }
        return chars;
    }

栈

由于条件为删除连续且重复的字符，故可以模拟栈结构来一次遍历

class Solution {
    public String removeDuplicates(String S) {
        StringBuffer stack = new StringBuffer();
        int top = -1;
        //模拟栈，发现字符就存入栈中，栈针加1，发现连续相同则删去并让栈针减一
        for (int i = 0; i < S.length(); ++i) {
            char ch = S.charAt(i);
            if (top >= 0 && stack.charAt(top) == ch) {
                stack.deleteCharAt(top);
                --top;
            } else {
                stack.append(ch);
                ++top;
            }
        }
        return stack.toString();
    }
}

一次遍历

• 时间复杂度
  O(n)
• 空间复杂度
  O(n) 或 O(1)，取决于使用的语言提供的字符串类是否提供了类似「入栈」和「出栈」的接口。注意返回值不计入空间复杂度。