def dict_contains(candidate: str, dictionary: list[str]) -> bool:
"""
Helper: check if a substring is in the dictionary.
Uses a simple list of strings and linear search.
"""
return candidate in dictionary
def segment_text(text: str, dictionary: list[str]) -> list[str]:
"""
This function performs the segmentation and returns the result.
It contains your original DP logic exactly as before.
"""
n = len(text)
# dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid
dp = [0] * (n + 1)
valid = [False] * (n + 1)
valid[0] = True # empty prefix is valid
for i in range(1, n + 1):
for j in range(i):
# Check whether dp[j] contains a valid split point;
# if it does, it means the prefix text[0:j] can be segmented.
if valid[j]:
candidate = text[j:i] # substring text[j:i]
# Verify whether this substring is a valid dictionary word.
if dict_contains(candidate, dictionary):
dp[i] = j
valid[i] = True
break
# If dp[n] is not valid, segmentation is impossible
if not valid[n]:
return []
# Backtrack to recover words
words = []
i = n
while i > 0:
j = dp[i]
words.append(text[j:i])
i = j
# Reverse the collected words
words.reverse()
return words
# Example usage
if __name__ == "__main__":
text = "thisisatestfoo"
# Example dictionary
dictionary = ["this", "is", "a", "test", "hello", "world", "foo", "bar"]
# Call the segmentation function
words = segment_text(text, dictionary)
# Print results
print("Segmentation result:")
for w in words:
print(w)
'''
Segmentation result:
this
is
a
test
foo
'''
