当前位置：首页 > article >正文

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

article 2025/2/22 5:07:20

leetcode 1047
在这里插入图片描述

思路

因为要删除字符串中的所有相邻重复项，那么在删除完成后，最后返回的元素中是不应该存在任何相邻重复项的，如果是普通的遍历，假设str = ‘abbaca’，遍历出来只发现中间的bb是相邻重复的删除了以后aaca又是重复的，又要去遍历，并且索引位置还会发生改变，这样想的话就复杂化了

所以怎样解决这个题更简单呢？

利用栈来解决本题，把遍历到的元素和栈顶元素进行比较，如果相等，那么说明是要消除的元素，如果不相等，那么要把从栈顶取出的元素先放回，然后把当前遍历的元素也放入，最终遍历完成后把栈中元素转为字符串即得到答案
让我们模拟一下操作，假设str = ‘abbaca’
1: item = a stack = [‘a’]
2: item = b stack = [‘a’,‘b’]
3: item = b stack.pop() = ‘b’ ✅ stack = [‘a’]
4: item = a stack.pop() = ‘a’ ✅ stack = []
5: item = c stack = [‘c’]
6: item = a stack = [‘c’, ‘a’]
result = ‘ca’

实现

function removeDuplicates(s: string): string {
    const stack = [];
    for(const item of s){
        const ele = stack.pop();
        if(ele !== item){
            stack.push(ele);
            stack.push(item)
        }
    }
    return stack.join('')
};