educative.io

Educative

More classic recursion approach

The code in the lesson also checks if second in dictionary which saves one recursion call for each pair, but makes it harder to understand. The more classic solution has explicit non-recursive branch and omits some checks as they are not required:

def can_segment_string(s, dictionary):
  if s in dictionary:
    return True
  for i in range(1, len(s) - 1):
    if s[0:i] in dictionary and can_segment_string(s[i:], dictionary):
        return True
  return False