Challenge: word break
Determine if a string can be segmented into dictionary words using bottom-up DP.
- Determine if a string can be segmented into dictionary words using DP
Optional challenge. These puzzles reward the right data structure choice — the test suite includes an efficiency check.
Given a string s and a list of dictionary words, return True if s can be
segmented into a space-separated sequence of one or more dictionary words.
word_break("leetcode", ["leet", "code"]) → True.
word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) → False.
A recursive approach without memoisation recomputes the same suffixes repeatedly, giving exponential time. DP brings it to O(n²).
Hint: use a boolean DP array where dp[i] is True if s[:i] can be
segmented. For each position i, look back at every j < i: if dp[j] is
True and s[j:i] is in the word set, set dp[i] = True. Start with
dp[0] = True (empty prefix).
Write word_break(s, word_dict) returning True if s can be segmented into words from word_dict. Use bottom-up DP with a boolean array.
word_break("leetcode", ["leet","code"]) → Trueword_break("catsandog", ["cats","dog","sand","and","cat"]) → False