Word Break
Problem statement
You get a string s with no spaces and a list of dictionary words wordDict. Return true if s can be split into a sequence of one or more dictionary words, and false otherwise.
Words may be reused any number of times, and every character of s must belong to exactly one word in the split. Picture tags or identifiers that were concatenated without separators and must be split back into known tokens.
Examples
Example 1
Input: s = "kubectlapply", wordDict = ["kube","kubectl","ctl","apply","app"]
Output: true
Explanation: Split it as "kubectl" + "apply". Starting with "kube" works too: "kube" + "ctl" + "apply".
Example 2
Input: s = "helmcharts", wordDict = ["helm","chart","art"]
Output: false
Explanation: Everything but the final "s" can be split, and no word covers that "s".
Hints
Approach
Bottom-up DP over prefixes. Put the words in a set and note the longest word length L. Let ok[i] mean s[:i] can be split, with ok[0] = True.
For each end i from 1 to n, check start positions j from i - 1 down to max(0, i - L): if ok[j] is true and s[j:i] is a word, set ok[i] = True and stop. The answer is ok[n].
Each of the n positions checks at most L candidate words, each costing O(L) to slice and hash.
O(n · L²)Space O(n + dictionary size)def word_break(s, word_dict): words = set(word_dict) longest = max(map(len, words), default=0) ok = [True] + [False] * len(s) for i in range(1, len(s) + 1): for j in range(i - 1, max(0, i - longest) - 1, -1): if ok[j] and s[j:i] in words: ok[i] = True break return ok[len(s)] print(word_break("kubectlapply", ["kube", "kubectl", "ctl", "apply", "app"]))print(word_break("helmcharts", ["helm", "chart", "art"]))Follow-up questions
- Return every possible split as sentences (Word Break II, memoised backtracking).
- Return a split that uses the fewest words.
Frequently asked questions
Tokenising text against a known vocabulary shows up in log and metric-name parsing, splitting concatenated identifiers, and command parsing. As an interview problem, it is a clean check that you can turn a backtracking search into a DP over prefixes once you notice the same suffixes being solved repeatedly.
A dictionary word can't be longer than L, so any slice s[j:i] longer than that can't match. Skipping those slices turns the inner loop from O(n) into O(L) without changing the result.
Yes. From each reachable position j, walk a trie of the words along s[j:] and mark every position where a word ends. That avoids building substrings and hashing them, which helps when words are long or numerous.