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

LeetCode LeetCode 栈 字符串
发布时间 :
字数:1.7k 阅读 : 评论:
  1. 1047.删除字符串中的所有相邻重复项
    1. 1047.1 题目
    2. 1047.2 题解
      1. 方法一：StringBuilder 模拟栈
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：字符数组模拟栈
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 1047.3 代码
    4. 1047.4 运行结果

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

1047.1 题目

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

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

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

示例：

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

提示：

  • 1 <= S.length <= 20000
  • S 仅由小写英文字母组成。

1047.2 题解

方法一：StringBuilder 模拟栈

思路

这道题的关键是「消除相邻重复项」，而且消除后可能产生新的相邻重复项。栈非常适合处理这种场景：遇到与栈顶相同的字符就弹出，否则压入。

用 StringBuilder 模拟栈：遍历字符串，如果当前字符与「栈顶」（即 StringBuilder 最后一个字符）相同，就删除栈顶；否则追加当前字符。

举个例子：输入 "abbaca"

遍历过程：
- 遇到 'a'：栈空，入栈 → "a"
- 遇到 'b'：栈顶 'a' ≠ 'b'，入栈 → "ab"
- 遇到 'b'：栈顶 'b' == 'b'，出栈 → "a"
- 遇到 'a'：栈顶 'a' == 'a'，出栈 → ""
- 遇到 'c'：栈空，入栈 → "c"
- 遇到 'a'：栈顶 'c' ≠ 'a'，入栈 → "ca"

最终结果："ca"

复杂度分析

  • 时间复杂度：O(n)，每个字符最多入栈出栈各一次
  • 空间复杂度：O(n)，最坏情况下栈中存储所有字符

代码

// 方法一：StringBuilder模拟栈
// 使用 StringBuilder 模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
static string RemoveDuplicates1(string s)
{
    // 创建 StringBuilder 对象，用于模拟栈的操作
    StringBuilder stack = new StringBuilder();

    // 遍历输入字符串的每个字符
    foreach (char c in s)
    {
        // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
        if (stack.Length > 0 && stack[stack.Length - 1] == c)
        {
            stack.Remove(stack.Length - 1, 1); // 出栈
        }
        else
        {
            stack.Append(c); // 入栈
        }
    }

    // 将 StringBuilder 转换为字符串并返回
    return stack.ToString();
}

方法二：字符数组模拟栈

思路

与方法一思路相同，但用字符数组模拟栈可以避免 StringBuilder.Remove 的开销。

用 top 指针标记栈顶位置：入栈时 stack[top++] = c，出栈时 top--。

具体步骤：

  1. 创建字符数组 stack，top = 0 表示栈顶
  2. 遍历字符串每个字符
  3. 如果栈不为空且当前字符等于栈顶，出栈（top--）
  4. 否则入栈（stack[top++] = c）
  5. 最终返回 new string(stack, 0, top)

举个例子：输入 "abbaca"

字符数组操作：
- 'a'：top=0，入栈，stack=['a'], top=1
- 'b'：top=1，stack[0]='a'≠'b'，入栈，stack=['a','b'], top=2
- 'b'：top=2，stack[1]='b'=='b'，出栈，top=1
- 'a'：top=1，stack[0]='a'=='a'，出栈，top=0
- 'c'：top=0，入栈，stack=['c'], top=1
- 'a'：top=1，stack[0]='c'≠'a'，入栈，stack=['c','a'], top=2

返回 new string(stack, 0, 2) = "ca"

复杂度分析

  • 时间复杂度：O(n)，每个字符最多入栈出栈各一次
  • 空间复杂度：O(n)，字符数组大小与输入相同

代码

// 方法二：字符数组模拟栈
// 使用字符数组模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
static string RemoveDuplicates2(string s)
{
    // 创建字符数组作为栈，top 表示栈顶位置
    char[] stack = new char[s.Length];
    int top = 0;

    // 遍历输入字符串的每个字符
    foreach (char c in s)
    {
        // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
        if (top > 0 && stack[top - 1] == c)
        {
            top--; // 出栈
        }
        else
        {
            stack[top++] = c; // 入栈
        }
    }

    // 将字符数组转换为字符串并返回，只取栈中有效元素部分
    return new string(stack, 0, top);
}

1047.3 代码

using System;
using System.Text;

class Program
{
    static void Main()
    {
        #region 题目

        // 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
        // 在 S 上反复执行重复项删除操作，直到无法继续删除。
        // 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

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

        // 提示：
        // 1 <= S.length <= 20000
        // S 仅由小写英文字母组成。

        #endregion

        #region 测试

        // 示例测试
        string str1 = "abbaca";
        string result1_1 = RemoveDuplicates1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        string result1_2 = RemoveDuplicates2(str1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 添加更多测试用例...

        #endregion
    }

    #region 答案

    // 方法一：StringBuilder模拟栈
    // 使用 StringBuilder 模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
    static string RemoveDuplicates1(string s)
    {
        // 创建 StringBuilder 对象，用于模拟栈的操作
        StringBuilder stack = new StringBuilder();

        // 遍历输入字符串的每个字符
        foreach (char c in s)
        {
            // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
            if (stack.Length > 0 && stack[stack.Length - 1] == c)
            {
                stack.Remove(stack.Length - 1, 1); // 出栈
            }
            else
            {
                stack.Append(c); // 入栈
            }
        }

        // 将 StringBuilder 转换为字符串并返回
        return stack.ToString();
    }

    // 方法二：字符数组模拟栈
    // 使用字符数组模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
    static string RemoveDuplicates2(string s)
    {
        // 创建字符数组作为栈，top 表示栈顶位置
        char[] stack = new char[s.Length];
        int top = 0;

        // 遍历输入字符串的每个字符
        foreach (char c in s)
        {
            // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
            if (top > 0 && stack[top - 1] == c)
            {
                top--; // 出栈
            }
            else
            {
                stack[top++] = c; // 入栈
            }
        }

        // 将字符数组转换为字符串并返回，只取栈中有效元素部分
        return new string(stack, 0, top);
    }

    #endregion
}

1047.4 运行结果

示例1 方法1 输出：ca
示例1 方法2 输出：ca
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏