字符串操纵递归函数

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

我需要一个基址，如果这种情况可以解释这一点，但我找不出一个，我的算法有什么问题吗？在

Answer 1

密码的出现，对吧？：-）怎么样

while True:
    backup = input
    for letter in string.ascii_lowercase: input = input.replace(letter * 2, '')
    if backup == input: break

是吗？在

Answer 2

为了回答您上面的问题，正如@Bhathiya Perera在评论中强调的那样，执行递归调用需要一个退出条件，首先，这样代码不会永远运行，而且还要定义一个令人满意的返回。在

在您的例子中，退出条件是字符串不再包含可以扩展到的重复项，我不能删除更多的字符，或者输入字符串=输出字符串。在

进一步的注释是，如果退出条件定义良好，则可以使用for循环，而不必担心对函数的无休止的调用。在

def remove_adjacent_duplicates(input_string): 
    '''
    Function removes adjacent duplicates recursively
    '''
    string_length = len(input_string)
    # If length of string is 1 or 0 then there are no duplicates present
    if string_length == 0 or string_length == 1: 
        return input_string 

    # Iterate through the string to remove all duplicates present in first pass
    # Note that the range goes from 1 -> len-1 to avoid boundary errors
    for i in range(1, string_length - 1):
        if input_string[i-1] == input_string[i]:
            # Remove duplicates by slicing the string around the duplicates
            new_string = input_string[:i - 1] + input_string[i + 1:]
            print new_string

    if new_string == input_string:
        #  Define the exit condition 
        return input_string
    else:
        # Recursive call if there have been duplicate removals
        # This will do a final call to ensure no more duplicates remain 
        return remove_adjacent_duplicates(new_string)

Answer 3

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

这将导致

^{pr2}$