时间戳

首页 > 解决方案 > 字符串操作递归函数

python - 字符串操作递归函数

问题描述

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

例如"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")

我需要一个基础，如果案例可以解释这一点，但我无法弄清楚，我的算法有问题吗？

标签： pythonstringpython-3.xrecursion

解决方案

您需要转换直到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

推荐阅读