Word Break Problem

from typing import List
 
 
def wordBreak(s: str, dictionary: set[str], m: int) -> List[object]:
    """
    :param s: input string that needs to be segmented
    :param dictionary: set of dictionary words
    :param m: max length of a word in the dictionary
 
    :return: a list of two objects
    1. True if the string can be segmented into dictionary words, False otherwise
    2. A list of integers representing the partitioning of the string into dictionary words
 
    n = len(s)
    Time complexity: O(n * min(n, m))
    Space complexity: O(n)
 
    note: the complexity is not considering the dictionary space and lookup time
 
    """
 
    # dp[i] = true, if string s[0...i] can be segmented into dictionary words
    dp = [False for i in range(len(s) + 1)]
 
    # partition[i] = j, where s[j:i] is a dictionary word
    partition = [-1 for i in range(len(s) + 1)]
 
    # dp[0] = true, because an empty string can always be segmented.
    dp[0] = True
 
    # Iterate over the prefixes s[0...i]
    for i in range(1, len(s) + 1):
        # Iterate over the prefixes s[j...i] where j < i and i - j <= m
        for j in range(i-1, max(-1, i-m-1), -1):
            if dp[j] and s[j: i] in dictionary:
                dp[i] = True
                partition[i] = j
                break
 
    return [dp[len(s)], partition]
 
 
def print_partitioned_substrings(s, partition, i):
    if i == 0 or partition[i] == -1:
        return
    print_partitioned_substrings(s, partition, partition[i])
    print(s[partition[i]:i])
 
 
# Example
dict = set({"apple", "pen", "pineapple", "I", "like"})
m = 9  # max length of a word in the dictionary
 
for s in ["Ilikepineapple", "catsandlionsanddog"]:
    can_segment, partition = wordBreak(s, dict, m)
    if can_segment:
        print_partitioned_substrings(s, partition, len(s))
    else:
        print(f"String '{s}' cannot be segmented into dictionary words.\n")