字符串的相邻字符去重

[编程题]字符串的相邻字符去重

热度指数：1597 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个仅由英文小写字母组成的字符串 $s$ ，将相邻且相同的两个字符删掉构成新的字符串，重复删除操作直至生成不符合删除条件的字符串并返回。

$1\leq s.length \leq 2*10^4$

示例1

输入

"bcaac"

输出

"b"

说明

bcaac执行删除操作后变为bcc，再次执行删除操作变为b，此时不再符合删除条件故返回b。

示例2

输入

"ab"

输出

"ab"

说明

原串即不符合删除条件，故直接返回。

示例3

输入

"bcaaac"

输出

"bcac"

说明

bcaaac执行删除操作后变为 bcac ，此时不再符合删除条件

算法知识视频讲解

Java

西方不胜

//使用char数组模拟栈，提升空间和时间性能

int index = -1;

        char[] chs = new char[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if(index != -1 && chs[index] == s.charAt(i)) {
                index--;
            }else {
                chs[++index] = s.charAt(i);
            }
        }
        return new String(chs, 0, index + 1);

发表于 2022-08-27 19:09:02 回复(0)