当前位置:网站首页>LeetCode——1047. 删除字符串中的所有相邻重复项

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

2022-08-06 07:45:55豌豆二锅头

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

题目

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

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

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

思路

其实可以看成一个栈,如果栈顶,次顶一样,那么就弹出栈顶和次顶,最后在栈中的,其实就是最终结果的所有字符。

代码

class Solution {
    
    public String removeDuplicates(String s) {
    
        // s 仅由小写字母组成
        char[] word = s.toCharArray();
        int length = s.length();
        int top = -1;
        for (int i = 0; i < length; ++i)
        {
    
            if (top==-1 || word[top]!=word[i])
            {
    
                word[++top]=word[i];
            }
            else
                top--;
        }
        return String.valueOf(word,0,top+1);
    }
}

结果

在这里插入图片描述
一个比较巧妙的利用栈来解决问题的过程,利用一个栈顶指针,如果,当前的位置的字符和栈顶指针的不相同,那么将当前位置的字符复制到栈顶指针的下一个位置。
如果当前位置的字符和栈顶指针的相同,那么就越过这两个字符,把top指针往左降低一个位置。并重新比对top和下一个位置的字符的情况。

原网站

版权声明
本文为[豌豆二锅头]所创,转载请带上原文链接,感谢
https://blog.csdn.net/weixin_44750790/article/details/126159748

随机推荐