solution.py

#https://pytrie.readthedocs.io/en/latest/#trie-methods
from pytrie import SortedStringTrie as Trie

s = Trie(the=0, do=1, dog=2, ate=3, gate=4, cat=5)
print('example:',s)
print('prefixes example:',s.keys(prefix='do'))

sentence = "thedogatethecat"

def generator_string(s):
    n = len(s)
    i = 0
    while i < n:
        yield s[i]
        i += 1
        
g = generator_string(sentence)

print('starting..')
possible_sentences = {}
def recoursive(sentence, possible_sentences):
  print('\nrecoursively working on string:',sentence)
  word = ''  
  for idx, letter in enumerate(sentence):
      word+=letter 
      print('progress:', word)
      prefixes = s.keys(prefix=word)      
      if len(prefixes)>0:        
        for i in range(0,len(prefixes)):
          if word==prefixes[i]:
            print ('found:', prefixes,'for:', word)
            print('possible sentences',possible_sentences)
            possible_sentences[word] = {}
            print('possible sentences',possible_sentences)
            print('s:',sentence[idx+1:],'poss:',possible_sentences[word])
            recoursive(sentence[idx+1:],possible_sentences[word])
  print('returning..')

recoursive(sentence, possible_sentences)
print('the do',possible_sentences['the']['do'])
print('the dog',possible_sentences['the']['dog'])