Python编程题35--删除字符串中的所有相邻重复项

题目

给定仅由小写字母组成的非空字符串，存在一个重复项删除操作，其会选择两个相邻且相同的字母，并删除它们。

请在字符串上反复执行重复项删除操作，直到无法继续删除，并在完成所有重复项删除操作后返回最终的新字符串。

例如：

给定一个字符串：aaabbaaaca，返回结果：ca

给定一个字符串：a，返回结果：a

实现思路1

• 使用 双指针 来实现
• 设置两个指针：slow、fast，初始值均为 0 ，同时用列表res存放字符串中所有字符
• 当 fast 小于字符串的长度时，执行循环，每次循环都把res中 fast 对应的字符放到 slow 指针下，并让 fast + 1
• 每次循环中，判断 slow 对应字符是否等于前一个字符。如果等于那么让 slow - 1，以便下次循环时重新设置res中 slow 前一个位置对应的字符，否则就让 slow + 1
• 当 fast 等于字符串的长度时，退出循环，此时 res 中从索引 0 到 slow 对应的所有字符，就是最终相邻不重复的字符，将其拼接为一个新字符串返回即可

代码实现1

def removeDuplicates(s):
    res = list(s)
    slow, fast = 0, 0
    while fast < len(s):
        res[slow] = res[fast]
        if slow > 0 and res[slow] == res[slow - 1]:
            slow -= 1
        else:
            slow += 1
        fast += 1
    return "".join(res[0:slow])

实现思路2

• 使用 栈 来实现
• 设置一个栈，用一个列表res来模拟
• 遍历字符串，如果res为空，则直接把当前字符添加到res；如果res非空且最后一个字符，恰等于当前字符，也就说明出现重复项需删除，于是对 res 执行出栈操作
• 遍历结束后，res中存放的就是最终相邻不重复的字符，将其拼接为一个新字符串返回即可

代码实现2

def removeDuplicates(s):
    res = []
    for i in s:
        if res and res[-1] == i:
            res.pop()
        else:
            res.append(i)
    return "".join(res)

更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）