leetcode
leetcode 1001 ~ 1050
删除字符串中的所有相邻重复项

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

难度:

标签:

题目描述

代码结果

运行时间: 38 ms, 内存: 16.8 MB


/*
 * 思路:
 * 使用栈数据结构并结合Java Stream来解决这个问题。
 * 首先,将字符流化并遍历。对于每个字符,如果栈不为空且栈顶字符与当前字符相同,则弹出栈顶字符。
 * 否则,将当前字符压入栈中。
 * 最终,使用Stream将栈中的字符连接成字符串。
 */

import java.util.Stack;
import java.util.stream.Collectors;

public class Solution {
    public String removeDuplicates(String S) {
        Stack<Character> stack = new Stack<>();
        S.chars().mapToObj(c -> (char) c).forEach(c -> {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        });
        return stack.stream()
                     .map(String::valueOf)
                     .collect(Collectors.joining());
    }
}

解释

方法:

这个题解采用了栈的数据结构来处理问题。遍历字符串中的每个字符,使用栈来暂存字符。如果栈顶的字符和当前遍历到的字符相同,则弹出栈顶字符(相当于删除两个相邻的相同字符)。如果不同,则将当前字符压入栈。这样,遍历完整个字符串后,栈中剩余的字符顺序就是删除所有相邻重复项后的结果。最后,将栈中的字符连接成字符串作为结果返回。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在处理字符串的时候,栈的使用是出于什么考虑?为什么选择栈而不是其他数据结构如队列或链表?
栈是一种后进先出(LIFO)的数据结构,这使得它在处理类似删除相邻重复项的问题时非常有效。当处理字符串时,遇到与栈顶相同的字符,可以立即将栈顶元素弹出,这样可以方便地撤销前一步的操作,与问题要求的连续消除动作直接对应。如果使用队列(先进先出),则需要访问整个数据结构来找到需要删除的元素,效率较低。链表虽然可以从任何位置增加或删除元素,但在这种具体问题中,需要额外的指针操作和遍历,不如直接使用栈来得直接和高效。
🦆
如果栈顶元素与当前字符相同就进行弹栈操作,这种方法处理字符串中间部分的连续重复字符时是否有效?例如如何处理'abba'这样的字符串?
这种方法同样适用于处理字符串中间的连续重复字符。以'abba'为例,处理过程如下:字符'a'被推入栈,接着'b'被推入栈,再次遇到'b'时,发现栈顶元素也是'b',因此弹栈。之后,字符'a'进栈,与栈顶的'a'相同,再次弹栈。最终栈为空,表示所有连续重复的字符都被有效删除。
🦆
栈操作中,字符被推入和弹出栈都算作一次操作,那么这种方法的总操作次数是否就是2n,其中n是字符串长度?
总操作次数最多为2n,但实际上可能少于这个数。每个字符最多被推入栈一次和从栈中弹出一次。然而,并不是所有字符都会发生弹栈操作。只有当当前字符与栈顶字符相同时才会弹栈,因此实际操作数取决于输入字符串中相邻重复字符的分布情况。如果字符串中没有任何相邻的重复字符,那么只有n次推入操作,没有弹出操作。
🦆
在实际应用中,这种方法在处理非常长的字符串时的性能如何?是否有可能因为频繁的栈操作而导致性能瓶颈?
在实际应用中,这种方法的时间复杂度是O(n),其中n是字符串的长度,这意味着它可以有效地处理长度较大的字符串。尽管栈操作涉及到频繁的推入和弹出,但每个操作的时间复杂度都是O(1),因此总体上是高效的。然而,如果栈的实现不当或者在极端情况下(如极大的字符串或特殊的硬件限制),可能会有性能瓶颈,比如内存消耗过大。在大多数标准应用场景中,这种方法是有效且性能是可接受的。

相关问题