Is it possible to delete/ignore all items on recursion/call stack, when I have hit a certain conditi-CodePudding

I am answering a question where we are given 3 strings: one, two and three. We want to return a Boolean to say whether we can create string three by interweaving strings one and two.

For example:

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

Whereas

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

My approach is two simply create three pointers pointing at the start of the three strings. And increment them one by one, when we find a match between strings one and three or two and three.

The above becomes tricky when pointer_one and pointer_two point to the same character in one and two respectively! In this case, we need to run a recursion. Now my question is when we start adding recursion calls to the recursive stack. We may get to a point where we reach the end of string three, and can return True for the overall function.

HOWEVER, there are still (partially complete) recursive calls in our recursion stack! And so the this latest return True, will be passed back to the previous caller, but I want to just return True for the whole function and ignore the remaining items in the recursion stack- is there anyway to do this?

Or would I have to write code in such a way as to simply return nothing until the stack is empty, and then return True to the final call?

The code I have written is quite long so I have omitted it for now but I can include it if necessary.

Thanks!

My code:

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

CodePudding user response：

This should be part of your recursive function's structure. When you make the recursive call, if it returns True, return from the current call with a value of True.

For example:

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

Observations on your code:

The result from possible_interwoven = interweavingStrings(...) is more definitive than just a possibility. When you obtain True from that call, you are certain that the rest of the characters are interwevable. So you should return True immediately when possible_interwoven is True. This will automatically trickle up the recursive call to produce the final result.

There are also issues with how you advance your pointers but I can't see an easy way to fix that with a simple tweak.

here's a revised version using your pointer approach:

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)