如何实现字符串中相邻大小写配对相同字母对的消除功能？

实现思路 #

这种需要处理「消除后产生新相邻配对」的场景，最适合用栈结构实现，逻辑如下：

• 初始化一个空栈保存遍历过程中未配对的字符
• 逐个遍历输入字符串的每个字符：
  • 如果栈不为空，取栈顶字符和当前字符对比，若两者是同一字母的大小写配对（转小写/大写后相等，且本身大小写不同），则弹出栈顶字符（相当于两个字符配对消除）
  • 不符合消除条件就把当前字符压入栈
• 遍历完成后将栈内字符拼接为字符串就是最终结果

原代码错误点 #

你写的代码存在几个明显问题：

• 变量名拼写错误：第一个for循环的迭代变量是小写i，却往列表里添加了未定义的大写I，直接会触发NameError
• 概念混淆：第二个循环中的c是索引值，你却直接拿ord(c)计算字符编码，还把索引值直接拼接到结果字符串里，逻辑完全不成立
• 判断逻辑错误：大小写配对的判断逻辑写得完全不对，正确判断应该是两个字符转小写后相等且本身不相等
• 未考虑消除后的新配对：比如示例中的AbBa，消掉中间的bB后，剩下的Aa也需要消除，单次逐位遍历根本覆盖不了这种场景

修复后代码 #

def decode(c_p):
    stack = []
    for char in c_p:
        if stack:
            top_char = stack[-1]
            # 判断是否为同一字母的大小写配对
            if top_char.lower() == char.lower() and top_char != char:
                stack.pop()
                continue
        stack.append(char)
    return ''.join(stack)

验证效果 #

print(decode("AbBax")) # 输出 x
print(decode("cCdatabasacCADde")) # 输出 database

完全符合你给出的示例要求。

内容的提问来源于stack exchange，提问作者João