Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of one or more dictionary words. e.g. s='leetcode', dict=['leet','code'] → true.
Spotting that 'can this be partitioned' over a string is a 1D DP where each position asks whether some prior cut point is reachable and the gap between them is a valid word.
Segmentation/partition questions on a string map to a boolean 1D DP: dp[i] = 'the prefix s[0..i) can be fully segmented'. dp[0] = true (empty prefix). For each end i, look back to every cut j < i: if dp[j] is true and s[j..i) is in the dictionary, then dp[i] is true. The answer is dp[n]. Put the dictionary in a Set for O(1) membership. This is O(n^2) cut points times the substring/lookup cost. The recognition signal is 'break/segment/partition a string using pieces from a set' → dp over prefix-reachability; the same shape solves word-break-II (store the actual cuts) and decode-ways where the 'dictionary' is implicit. A common optimisation caps the inner loop by the longest dictionary word.
Deciding if a string can be split into allowed pieces (or counting such splits) → dp[i] = prefix s[0..i) is reachable, transition over cut points with a Set lookup.
Time O(n²·k) · Space O(n) (k = substring cost)