The tell: Can a string be split into dictionary words — a decision over every split point.
How you get there
1dp[i] is true when s[:i] can be segmented.
2dp[i] holds if some j < i has dp[j] true and s[j:i] is in the dictionary.
3Greedy longest-match fails, which is why the DP explores every split.
Solution
Python
def word_break(s: str, word_dict: list[str]) -> bool:
words = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[len(s)]
Time
O(n² · L)
Space
O(n)
What goes wrong
Greedy matching of the longest word fails on 'aaaaab' with ['aaaa', 'aaa', 'b'].