python - 字符串操作递归函数

Question

努力实现递归转换函数，该函数将从字符串中删除连续的重复字母...

例如 "abbabcc"=> "aabcc"(在第一次通过时，删除 "bb")

例如 "aabcc"=> "bcc"(在第二次传递时，删除 "aa")

然后递归调用自身直到最终归约类似于"abbabcc"=> "b"

def transformations(J):
    if len(J) == 1:
        return J
    front_part = ""
    back_part = ""
    if J[0] == J[1]:
        back_part += J[2:]
        return transformations(back_part)
    else: 
        front_part += J[0]
        back_part += J[1:]
        return front_part + transformations(back_part)

assert transformations("ab") == "ab"
assert transformations("aba") == "aba"
assert transformations("abc") == "abc"
assert transformations("aabbbccaaba") == "a"


assert transformations("abba") == "" 
# "abba" should return "aa" on first pass then return empty string 
# on second pass, but right now it returns "aa" and stops there

现在，上述算法适用于大多数输入，除了中间有双连续的输入，在删除第一个连续后会产生另一个双连续，例如 ("abba")

我需要一个 base if case 来解释这个问题，但我想不出来，我的算法有问题吗？

Answer 1

你需要转换直到input == result。当 input == result 时，这意味着它不能再转换。请参阅下面的更改。

def transformations(J):
    if len(J) <= 1: # I made it less than or equal
        return J
    front_part = ""
    back_part = ""
    if J[0] == J[1]:
        back_part = J[2:]
        return transformations(back_part)
    else: 
        front_part = J[0]
        back_part = J[1:]
        # See below
        result =  front_part + transformations(back_part)
        # If it's same we have done all transformations.
        if result == J:
            return result
        else: # try to perform more transformations
            return transformations(result)

tests = [
    ["abba", ""],
    ["ab", "ab"],
    ["aba", "aba"],
    ["aabbbccaaba", "a"]
]

for inp, expected in tests:
    actual = transformations(inp)
    print("trans(%s) == %s" % (inp, actual), "Test Passed =", actual == expected)

这将导致

trans(abba) ==  Test Passed = True
trans(ab) == ab Test Passed = True
trans(aba) == aba Test Passed = True
trans(aabbbccaaba) == a Test Passed = True