Word Break

Problem

Search engines tokenize user queries by splitting raw input into recognized vocabulary terms before looking up the index. Given a string s and a list of dictionary words, return True if s can be segmented into a sequence of dictionary words (words may be reused).

Input: s="leetcode", words=["leet","code"]          → True
Input: s="applepenapple", words=["apple","pen"]     → True
Input: s="catsandog", words=["cats","dog","sand","and","cat"]  → False

Verification

Trace 'leetcode' with ['leet','code']: dp=[T,F,F,F,F,F,F,F,F]. i=4: j=0, dp[0]=T and s[0:4]='leet' in set -> dp[4]=T. i=8: j=4, dp[4]=T and s[4:8]='code' in set -> dp[8]=T. Return True.

Solution

Approach: 1D reachability DP over string prefixes.

Define dp[i] as True when the prefix s[0:i] can be fully segmented into dictionary words. The empty prefix is trivially segmentable, so dp[0] = True is the base case. To decide dp[i], look for a split point j < i where two things hold: the prefix up to j is already segmentable (dp[j] is True) and the remaining slice s[j:i] is itself a dictionary word. If any such j exists, the prefix s[0:i] is segmentable, so dp[i] = True. The inner loop breaks on the first qualifying j because one valid split is enough - reachability needs only existence, not a count. Converting word_dict to a set up front makes the s[j:i] in word_set membership test fast. The final answer is dp[n], which asks whether the whole string is reachable. Trace leetcode with ['leet','code']: dp[4] becomes True via the leet prefix from dp[0], then dp[8] becomes True via code from dp[4], so the function returns True. catsandog fails because no chain of splits reaches dp[9].

Edge cases: An empty string returns dp[0] = True. A word that overshoots or has no matching split leaves later cells False, so a string like catsandog correctly returns False even though many prefixes are segmentable.

Complexity: O(n^2) time (the i/j double loop) plus the slice-and-hash cost per check, O(n) space for the boolean array.