<jupyter_start><jupyter_text>Word Break II<jupyter_code># Time: O(n^3)
# Space: O(n)

def word_break(word, dictionary):
    def word_break_combination(word, text = []):
        if not word:
            res.append(' '.join(text))
            return
        for i in range(1, len(word) + 1):
            w = word[:i]
            if w in dictionary:
                word_break_combination(word[i:], text + [w])
    res = []
    word_break_combination(word)
    return res

if __name__=='__main__':
    print(word_break("applepenapple", ["apple", "pen"]))<jupyter_output>['apple pen apple']
{'fraction_non_alphanumeric': 0.14675767918088736, 'fraction_numerical': 0.005119453924914676, 'mean_word_length': 2.738853503184713, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '527594', 'license': 'MIT', 'n_tokens_mistral': 207, 'n_tokens_neox': 203, 'n_words': 45, 'path': 'assignments/dynamic_programming/Word Break Using Memoization.ipynb', 'repo_name': 'Anjani100/logicmojo', 'size': '586'}