面试题-python3 字符串消消乐，将字符串中相邻相同的字符一起消掉

上海-悠悠

发布于 2021-04-26 09:58:15

3K0

发布于 2021-04-26 09:58:15

文章被收录于专栏：从零开始学自动化测试

题目

字符串消消乐，将字符串中相邻相同的字符一起消掉，最后输出消除完成的字符串

示例：abcccbxezzzrf7788fn 输出：axern

说明：从左住右消除，第一趟消除相邻相同的“ccc”、“zzz”、“77”、“88”，得到abbxerffn，第二趟消除相邻相同的“bb”、“ff”，得到axern，不存在相邻相同字符，消除结束。

只删除2个相邻的字母

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

输入：”abbaca” 输出：”ca” 解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

# 作者-上海悠悠 QQ交流群:717225969
# blog地址 https://www.cnblogs.com/yoyoketang/

S = 'abbaca'
st = []

for i in S:
    if len(st) == 0:
        st.append(i)
    elif i == st[-1]:
        st.pop()
    else:
        st.append(i)
print("".join(st))

运行结果会得到：ca 如果只考虑相邻2个元素一样，这样消除是没问题的，如果考虑到相邻的3个元素一样也删除，就不能满足需求了如 S = ‘abbbaca’

相邻相同的字符一起消掉

在前面的基础上加个判断，判断元素是否与上一个被消除的元素一样（相邻多个元素相同也删除）

# 作者-上海悠悠 QQ交流群:717225969
# blog地址 https://www.cnblogs.com/yoyoketang/

a = "abcccbxezzzrf7788fn"
s = []
# 前一个被消除的元素
del_str = ''
for i in a:
    # 栈为空，直接添加入栈
    if len(s) == 0:
        s.append(i)
    else:
        # 判断i 与被前一个被消除的元素是都相等
        if i == del_str:
            # 如果相等不做处理
            continue
        # 判断 i 与栈顶元素是否相等
        elif i == s[-1]:
            # 弹出栈顶元素
            del_str = s.pop(-1)
        else:
            # 入栈
            s.append(i)
print("".join(s))

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-04-18，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法