You need to enable JavaScript to run this app. 面试遇到字符串相邻重复字符成对移除问题:求动态输入适配逻辑
优惠活动
大模型
产品
解决方案
定价
更多

面试遇到字符串相邻重复字符成对移除问题:求动态输入适配逻辑

核心解法逻辑

这个题目要求的连续多轮移除相邻相同字符对的操作,最优实现不需要做反复整串扫描、删除后重新遍历的暴力逻辑,用栈结构可以单遍遍历输入就得到最终结果,时间复杂度为O(n),完全适配任意长度的动态输入,和题目规则的执行效果完全一致。

具体实现步骤

  • 初始化一个可动态扩容的栈结构(可用编程语言自带的动态数组模拟,不需要提前分配固定内存)
  • 按顺序逐字符读取输入字符串的内容:
    1. 若栈非空,且栈顶存储的字符和当前读取的字符完全相同,说明二者构成待移除的相邻重复对,直接弹出栈顶元素即可完成移除——这一步的消解效果和多轮迭代删除的逻辑完全等价,因为弹出栈顶后,新的栈顶和后续字符的相邻关系,和整串删除后重新扫描得到的相邻状态完全一致
    2. 若不满足相邻重复的判定条件,则将当前读取的字符压入栈中
  • 遍历完所有输入字符后,将栈内存储的元素按入栈顺序拼接,就是最终的输出结果

规则匹配验证

拿题目给出的两个示例验证逻辑:

  1. 输入abbcaddaee,逐字符走栈流程时,当读取到栈内已有的a之后碰到下一个a时直接弹栈的操作,就等价于题目描述里“首轮删除后得到acaa,再二次迭代移除相邻aa对”的效果,最终栈内剩余元素为a、c,拼接结果为ac,和题目给出的最终输出完全一致
  2. 输入aabbbcffjdddd,逐字符走栈流程后最终栈内剩余元素为b、c、j,拼接结果为bcj,和题目给出的最终输出完全一致

适配动态输入的优势

和“每轮删除完重复对就重新扫描整串”的暴力多轮方案相比,栈实现的逻辑有两个核心优势:

  • 不需要对输入串长度做提前限制,栈本身支持动态扩容,不管用户输入多长的字符串、临时调整输入内容,都可以逐字符喂入处理流程,完全适配动态输入场景
  • 单遍遍历即可完成所有消解操作,不需要反复扫描已生成的中间字符串,时间复杂度从最坏O(n²)优化到O(n),处理长输入的效率高很多

参考实现代码

def collapse_adjacent_pairs(s: str) -> str:
    stack = []
    for c in s:
        if stack and stack[-1] == c:
            stack.pop()
        else:
            stack.append(c)
    return "".join(stack)

内容的提问来源于stack exchange,提问作者Sivasankar Saravanan

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.27 22:15:03