时间戳

首页 > 解决方案 > 递归删除偶数的相邻重复字母的代码

python - 递归删除偶数的相邻重复字母的代码

问题描述

最近在一个现场编码测试中被要求写代码递归删除偶数相邻的字母。当时我写不了代码。后来我尽力了。我的逻辑和代码有什么问题?

例如 cbbbaaaabbbccc => cbbbbbbccc => cccc => 空字符串

例如 aabbc => bbc => c

例如 abbbccc => abbbccc - 因为没有字母在偶数中重复

编辑 - 我根据 Rory 的建议编辑了代码，但仍然不明白为什么在字符串变空后它会进入递归调用而不是退出循环

str = "cbbbaaaabbbccc"   


def remUtil(str):
i = 0
ind = 0
while i < (len(str)-1):
    j = 0
    if str[i] == str[i + 1]:
        j = i
        ind = i
        count = 0
        while j < len(str)-1 and str[j] == str[j + 1]:
            count = count + 1
            j = j + 1
            i = i + 1
        # if the no. of comparisons are odd then even letters compared
        if count % 2 != 0:
            str = str[:(ind)] + str[(ind + count) + 1:]
            #print(str)
            remUtil(str)


    else:
        i = i + 1

标签： pythonpython-3.xrecursion

解决方案

一个较短的版本，避免了对索引的操作：

def rm_even_duplicates(s):
    ls = list(s) + [None]
    tmp = [ls[0]]
    out = []
    for c in ls[1:]:
        if c != tmp[0]:
            if len(tmp) % 2 == 1:
                out.extend(tmp)
            tmp = []
        tmp.append(c)
    # The recursive part, if you want to do it that way;
    # that could as well have been a while loop
    if len(out) == len(s):
        return ''.join(out)
    else:
        return rm_even_duplicates(out)

一些示例和您的测试用例：

print(rm_even_duplicates('aaabbcdddd'))
# aaac
print(rm_even_duplicates('aaabbccaaadda'))
# aaaaaaa

assert rm_even_duplicates('cbbbaaaabbbccc') == ''
assert rm_even_duplicates('aabbc') == 'c'
assert rm_even_duplicates('abbbccc') == 'abbbccc'

推荐阅读