是否可以删除/忽略递归/调用堆栈上的所有项，当我已经达到某个条件并将True返回到整个函数中？

Question

我正在回答一个问题，在这里我们有三个字符串：one、two和three。我们希望返回一个布尔值，以说明是否可以通过string three 来创建字符串、one和two。

例如：

one = "aab", two = "aac", three = "aaab" -> this should return True 

鉴于

one = "abb", two = "acc", three = "aaab" -> this should return False

我的方法是两个简单地创建指向三个字符串开头的three pointers。当我们找到字符串one and three或two and three之间的匹配时，逐个增加它们。

当pointer_one和pointer_two分别指向one和two中的相同字符时，上述情况就变得棘手了！在这种情况下，我们需要运行一个recursion。现在我的问题是什么时候开始向recursive stack添加递归调用。我们可能会到达到 string three的末尾，以及的整体函数的return True。

但是，在递归堆栈中仍然有(部分完成的)递归调用！因此，这个最新的return True将被传回给上一个调用者，但是我只想对整个函数进行return True，而忽略递归堆栈中的其余项--这样做有吗？

或者，我必须以这样的方式编写代码，直到堆栈为空，然后才进行return，然后将return True传递到最后的调用。

我编写的代码相当长，所以我暂时省略了它，但如果有必要，我可以包括它。

谢谢!

我的代码：

def interweavingStrings(one, two, three, pointer_one=0, pointer_two=0, pointer_three=0):
    possible_interwoven = False

    while pointer_three < len(three):

        if one[pointer_one] == two[pointer_two]:
            possible_interwoven = interweavingStrings(one, two, three, pointer_one + 1, pointer_two, pointer_three + 1)

            if not possible_interwoven:
                possible_interwoven = interweavingStrings(one, two, three, pointer_one, pointer_two + 1,
                                                          pointer_three + 1)

            if not possible_interwoven:
                break

        if pointer_two <= len(two) - 1 and three[pointer_three] == two[pointer_two]:
            pointer_two += 1
            pointer_three += 1
            possible_interwoven = True

        if pointer_one <= len(one) - 1 and three[pointer_three] == one[pointer_one]:
            pointer_one += 1
            pointer_three += 1
            possible_interwoven = True

        if pointer_two <= len(two) - 1 and pointer_one <= len(one) - 1 and one[pointer_one] != three[pointer_three] and two[pointer_two] != two[pointer_two]:
            return False

    return possible_interwoven

Answer 1

这应该是递归函数结构的一部分。当您进行递归调用时，如果它返回True，则从当前调用返回值True。

例如：

def canweave(a,b,c):
    if not c : return True
    if len(a)+len(b)<len(c): return False 
    if a and a[0]==c[0] and canweave(a[1:],b,c[1:]):
        return True                                   # works with 1st of a
    if b and b[0]==c[0] and canweave(a,b[1:],c[1:]):
        return True                                   # works with 1st of b
    return canweave(a[1:],b[1:],c)    # try with other chars
                                      # return result from recursion

print(canweave("aab","aac","aaab")) # True
print(canweave("abb","acc","aaab")) # False

对您的代码的观察

possible_interwoven = interweavingStrings(...)的结果应该是确定的，而不仅仅是一种可能性。当您从该调用中获得True时，您必须确定其余的字符是“可交互的”。因此，当possible_interwoven为True时，您应该立即返回True。这将自动逐出递归调用，以生成最终结果。

在如何推进指针方面也存在一些问题，但我看不出用简单的调整来解决这个问题的简单方法。

下面是使用指针方法的修订版：

def interweavingStrings(one, two, three, 
                        pointer_one=0, pointer_two=0, pointer_three=0):
    if pointer_three == len(three): 
        return True
    if pointer_one >= len(one) and pointer_two >= len(two): 
        return False
    if pointer_one < len(one) and one[pointer_one] == three[pointer_three]:
        if interweavingStrings(one,two,three,
                               pointer_one+1,pointer_two,pointer_three+1):
            return True
    if pointer_two < len(two) and two[pointer_two] == three[pointer_three]:
        if interweavingStrings(one,two,three, 
                               pointer_one,pointer_two+1,pointer_three+1):
            return True
    return interweavingStrings(one,two,three, 
                               pointer_one+1,pointer_two+1,pointer_three)