面试遇到字符串相邻重复字符成对移除问题:求动态输入适配逻辑
核心解法逻辑
这个题目要求的连续多轮移除相邻相同字符对的操作,最优实现不需要做反复整串扫描、删除后重新遍历的暴力逻辑,用栈结构可以单遍遍历输入就得到最终结果,时间复杂度为O(n),完全适配任意长度的动态输入,和题目规则的执行效果完全一致。
具体实现步骤
- 初始化一个可动态扩容的栈结构(可用编程语言自带的动态数组模拟,不需要提前分配固定内存)
- 按顺序逐字符读取输入字符串的内容:
- 若栈非空,且栈顶存储的字符和当前读取的字符完全相同,说明二者构成待移除的相邻重复对,直接弹出栈顶元素即可完成移除——这一步的消解效果和多轮迭代删除的逻辑完全等价,因为弹出栈顶后,新的栈顶和后续字符的相邻关系,和整串删除后重新扫描得到的相邻状态完全一致
- 若不满足相邻重复的判定条件,则将当前读取的字符压入栈中
- 遍历完所有输入字符后,将栈内存储的元素按入栈顺序拼接,就是最终的输出结果
规则匹配验证
拿题目给出的两个示例验证逻辑:
- 输入
abbcaddaee,逐字符走栈流程时,当读取到栈内已有的a之后碰到下一个a时直接弹栈的操作,就等价于题目描述里“首轮删除后得到acaa,再二次迭代移除相邻aa对”的效果,最终栈内剩余元素为a、c,拼接结果为ac,和题目给出的最终输出完全一致 - 输入
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
相关产品推荐
相关产品推荐

