Return from recursive function immediately when a solution is found-CodePudding

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.

CodePudding user response：

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)

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

Use return:

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