Bug with returning a value from recursive function

Question

This was written in answer to a leetcode problem: given a string, return the minimum number of cuts needed to partition the string into palindrome substrings.

It may not be the most efficient way, but I decided to explore the possibilities as a graph, the idea being to only add nodes that can possibly be in a path that creates palindromic substrings. As I build the graph level by level, all I need to do is track which level I am on (0 for root (i.e. the original string), 1 for children of root and so on), and once I hit a node whose value is a palindrome, the current level is the required answer.

The bug I am getting is that instead of returning the level, I get a return value of None. The bug only occurs for some inputs. I have tried entering different inputs but cannot see a pattern nevermind determining the cause. Via debugging I know that the return statement is being executed when expected. Why is this happening? What is the problem?

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)

I have made sure the code is reaching the return value and terminating there. A sample of the debug I did by print statements:

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

Generators are a good use case for problems involving combinations and permutations. This is because we can easily get a partial or complete answer without needed to modify the search/traversal program. Below we write palindromify as a generator which finds all combinations of substrings palindromes -

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)

This demonstrates another fundamental programming practice: When you have a complex problem, you can make it easier to solve by solving several smaller sub-problems. Checking whether a particular string is a palindrome is a different task than breaking a string into palindrome substrings. Let's write is_palindrome as its own function -

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

Let's see the output of palindromify on your input -

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

And here it is with a slightly bigger input -

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

And with a palindrome as input -

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

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

You can see even a small string can yield many possible combinations. And so using a generator here is important because we can terminate the computation as soon as we get the first result. Since the algorithm is written to return the largest palindromes first, it should result in the fewest cuts -

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

Above return automatically halts palindromes and no computations happen beyond the first result, potentially saving significant time and space. Now let's see solve called on our example inputs -

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