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)
上一篇:35. 搜索插入位置


下一篇:2-5 修理牧场 (35 分)