Recursivey searching (segments of) a sentence in a lexicon (python)

This program should return True if it is possible to generate the given sequence x from a given list of segments seglist. After finding one possible solution it should stop.

I tried replacing and repositioning the return commands, but there’s always a different problem coming up.

def valid_sequence(x, seglist): 
    if x in seglist:
        return True

    for i in seglist:
        if x.startswith(i):
            return valid_sequence(x[len(i):], seglist)
    return False

This returns the correct Boolean for sequence 'abc'and seglist ['a', 'ab', 'bc', 'c'], ['a', 'b', 'c'], and ['ab', 'bc'], but not for seglist ['a', 'ab', 'c'] because obviously it’s going through the 'a' variant but won’t be successfull and stops before going through 'ab', which it should.

I ran it through pythontutor and I understood some of the problems, but I could not determine how to fix them.

How do I write it so that it continues with segment 'ab' after taking the unsuccessful path of 'a'? Maybe I’m missing something else too, given that I can’t wrap my head around this recursion.

Is it even remotely possible this way, or do I have to take a totally different approach?

>Solution :

You were very close on this one. The main problem is that you should not return immediately in the recursive step. Notice that it will return False after the first loop that it is called. Consequently, the whole function will return False as well.

Said that, you should return only if the result is True:

def valid_sequence(x, seglist): 
    if x in seglist:
        return True

    for i in seglist:
        if x.startswith(i):
            if valid_sequence(x[len(i):], seglist):
                return True
    return False

This will fix the problem you mentioned, but there’s one more to go. If x = 'abc' and seglist = ['ab', 'b', 'c'] the function will correctly return True. But it will also return True for x = 'abbc', x = 'abbbc' and so on. This happens because the ‘b’ is being used indefinitly. I suppose that’s a not desired behavior. To overcome this we create a copy of the list for new calls and eliminate the used element:

import copy

def valid_sequence(x, seglist): 
    if x in seglist:
        return True

    for i in seglist:
        if x.startswith(i):
            newlist = copy.deepcopy(seglist)
            newlist.remove(i)
            
            if valid_sequence(x[len(i):], newlist):
                return True
    return False