Return from recursive function immediately when a solution is found

Question

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        class solutionFound(Exception):
            pass
        
        def dfs(s):
            if len(s) == 0:
                raise solutionFound
            
            for i in range(len(wordDict)):
                if s.startswith(wordDict[i]):
                    dfs(s[len(wordDict[i]):])
        
        try:
            dfs(s)
            return False
        except solutionFound:
            return True

In the code above, I'm making a lot of recursive calls inside the function and I just want to return immediately when a solution is found. One way to go about it is to use exception, I was just wondering if there is another way to achieve this with minimal code.

you may be interested in `callcc` introduced in [this Q&A](https://stackoverflow.com/a/72031470/633183). the code can be easily converted to python. — Mulan, Jul 13 '22 at 01:12

score 1 · Accepted Answer · answered Jul 12 '22 at 15:32

Your code should return True as soon as the base case is reached or False whenever the recursion finishes without any successful result. By doing this, the recursion will stop when the first result is found.

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        
    def dfs(s):
        if len(s) == 0:
            return True
        
        for i in range(len(wordDict)):
            if s.startswith(wordDict[i]):
                if dfs(s[len(wordDict[i]):]):
                    return True

        return False
    
    return dfs(s)

score 0 · Answer 2 · answered Jul 12 '22 at 15:29

I'd write this as:

def wordBreak(self, s: str, wordDict: list[str]) -> bool:
    if len(s) == 0:
        return True
    
    return any(
        wordBreak(s[len(word):], wordDict)
        for word in wordDict
        if s.startswith(word)
    )

This allows the return True to just go all the way up the stack, the same as the raise, since the any will immediately stop and return in each stack frame once a True result is found in the deepest one.

Note that an inner "helper" is also now unnecessary since your outer function can just return the result of the recursion.

score 0 · Answer 3 · answered Jul 12 '22 at 15:29

0

if len(s) == 0:
    return True
if s.startswith(wordDict[i]):
    if dfs(s[len(wordDict[i]):]):
        return True

This doesn't stop every level of recursion immediately, but prevents each level from making any more recursive calls.

answered Jul 12 '22 at 15:29

Scott Hunter

48,888
12
60
101

Return from recursive function immediately when a solution is found

3 Answers3