当找到解时立即从递归函数返回

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

在上面的代码中，我在函数内部进行了很多递归调用，我只想在找到解决方案时立即返回。一种方法是使用异常，我只是想知道是否有另一种方法可以用最少的代码实现这一点。

Answer 1

您的代码应该在达到基本情况时立即返回True，或者在递归完成而没有任何成功结果时返回False。通过这样做,递归将停止当第一个结果发现。

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)

Answer 2

我会这样写:

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)
)

这允许return True像raise一样沿着堆栈往上走，因为一旦在最深处找到True结果，any将立即停止并返回每个堆栈帧。

注意，内部的"帮助"现在也没有必要了，因为外部函数可以只返回递归的结果。

Answer 3

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

这不会立即停止每一级递归，但可以防止每一级再进行递归调用。