从递归函数返回值的错误

Question

这是为了回答leetcode problem：给定一个字符串，返回将该字符串划分为回文子字符串所需的最小剪切数

这可能不是最有效的方法，但我决定将其作为一个图来探索，其想法是只添加可能位于创建回文子串的路径中的节点。当我逐级构建图形时，我所需要做的就是跟踪我所在的级别（0表示根（即原始字符串），1表示根的子级，依此类推），一旦我命中一个值为回文的节点，当前级别就是所需的答案

我得到的错误是，不是返回level，而是返回值None。该错误仅在某些输入中出现。我试过输入不同的输入，但看不到模式，也无法确定原因。通过调试，我知道return语句正在按预期执行。为什么会这样？有什么问题

class Node:
    def __init__(self, val='', children=None):
        self.val = val
        self.children = children if children else []

class Solution:
    def minCut(self, s: str) -> int:
        if s == s[::-1]:
            return 0
        
        def _create_graph(root, level):
            n = len(root.val)
            for i in range(1, n):
                substr = root.val[:i]
                if substr == substr[::-1]:
                    comp_of_substr = root.val[i:]
                    if comp_of_substr == comp_of_substr[::-1]:
                        return level # code is reaching here as expected, but None is being returned
                    child = Node(comp_of_substr)
                    root.children.append(child)
            for child in root.children:        
                _create_graph(child, level + 1)
            
        root = Node(s)
        return _create_graph(root, 1)

我已经确保代码达到返回值并在那里终止。我通过print语句进行的调试示例：

root.val='abccbc', num_cuts=1
n=6
    i=1
    substr='a'
        comp_of_substr='bccbc'
        child.val='bccbc' appended to root.val='abccbc' children
    root.children = ['bccbc']
    i=2
    substr='ab'
    root.children = ['bccbc']
    i=3
    substr='abc'
    root.children = ['bccbc']
    i=4
    substr='abcc'
    root.children = ['bccbc']
    i=5
    substr='abccb'
    root.children = ['bccbc']
root.val='bccbc', num_cuts=2
n=5
    i=1
    substr='b'
        comp_of_substr='ccbc'
        child.val='ccbc' appended to root.val='bccbc' children
    root.children = ['ccbc']
    i=2
    substr='bc'
    root.children = ['ccbc']
    i=3
    substr='bcc'
    root.children = ['ccbc']
    i=4
    substr='bccb'
        comp_of_substr='c'
            found solution with num_cuts=2 # the print statement that gave this is literally
                                           # above the 'return level'

Answer 1

对于涉及组合和置换的问题，生成器是一个很好的用例。这是因为我们不需要修改搜索/遍历程序就可以轻松获得部分或完整答案。下面我们将palindromify写为一个生成器，用于查找子字符串回文组的所有组合-

def palindromify(s, w = ""):
  if not s: return
  if not w and is_palindrome(s): yield (s,)
  yield from palindromify(s[1:], w+s[0])
  if w and is_palindrome(w):
    for p in palindromify(s, ""):
      yield (w, *p)

这演示了另一种基本的编程实践：当您有一个复杂的问题时，您可以通过解决几个较小的子问题使其更容易解决。检查特定字符串是否为回文与将字符串拆分为回文子字符串是不同的任务。让我们编写is_palindrome作为它自己的函数-

def is_palindrome(s):
  return len(s) < 2 or s[0] == s[-1] and is_palindrome(s[1:-1])

让我们看看palindromify在您的输入上的输出-

for p in palindromify("abccbc"):
  print(p)

('a', 'bccb', 'c')
('a', 'b', 'cc', 'b', 'c')
('a', 'b', 'c', 'cbc')
('a', 'b', 'c', 'c', 'b', 'c')

这是一个稍微大一点的输入-

for p in palindromify("abbadeeda"):
  print(p)

('abba', 'deed', 'a')
('abba', 'd', 'ee', 'd', 'a')
('abba', 'd', 'e', 'e', 'd', 'a')
('a', 'bb', 'adeeda')
('a', 'bb', 'a', 'deed', 'a')
('a', 'bb', 'a', 'd', 'ee', 'd', 'a')
('a', 'bb', 'a', 'd', 'e', 'e', 'd', 'a')
('a', 'b', 'b', 'adeeda')
('a', 'b', 'b', 'a', 'deed', 'a')
('a', 'b', 'b', 'a', 'd', 'ee', 'd', 'a')
('a', 'b', 'b', 'a', 'd', 'e', 'e', 'd', 'a')

以回文作为输入-

for p in palindromify("racecar"):
  print(p)

('racecar',)
('r', 'aceca', 'r')
('r', 'a', 'cec', 'a', 'r')
('r', 'a', 'c', 'e', 'c', 'a', 'r')

您可以看到，即使是一个小字符串也可以产生许多可能的组合。所以在这里使用生成器是很重要的，因为我们一得到第一个结果就可以终止计算。由于该算法是为了首先返回最大回文而编写的，因此它应该导致最少的剪切-

def solve(s):
  for p in palindromify(s):
    return len(p)-1

上面的return会自动停止palindromes，并且在第一个结果之外不会发生任何计算，这可能会节省大量的时间和空间。现在让我们看一下solve在我们的示例输入中调用-

print(solve("abbadeeda")) # 2
print(solve("abccbc")) # 2
print(solve("racecar")) # 0
print(solve("abcde")) # 4
print(solve("z")) # 0