Minimum Dictionary Segments

Given a string s and an array dictionary, split all of s into a sequence of dictionary words.
Return the minimum possible number of words in a complete split. Return -1 if no complete split exists. The empty string requires zero words.

Function
minimumDictionarySegments(s: String, dictionary: String[]) → int

Examples
Example 1
s = "applepie"
dictionary = ["apple","app","le","pie"]
return = 2
The split apple | pie uses two words. No dictionary word covers the entire string.
Example 2
s = "aaaa"
dictionary = ["a","aa","aaa"]
return = 2
Either a | aaa or aaa | a uses the minimum of two words.
Example 3
s = "catsandog"
dictionary = ["cats","dog","sand","and","cat"]
return = -1
Every possible prefix split leaves characters that cannot be covered by a dictionary word.

Constraints
0 <= s.length <= 2000
0 <= dictionary.length <= 2000
1 <= dictionary[i].length <= 50
s and every dictionary word contain lowercase English letters.
Duplicate dictionary words have no additional effect.

Define dp[i] as the minimum words needed to build the first i characters. Set dp[0] = 0 and everything else to infinity. For each i, try every dictionary word w that ends at i, meaning s.substring(i - len, i) equals w. Then dp[i] = min(dp[i], dp[i - len] + 1). Answer is dp[n] or -1 if it's still infinity. Put the words in a hash set and loop over lengths 1 to 50 instead of scanning all 2000 words. That gives about 2000 * 50 substring checks, which is fine. The common pitfall is greedy: taking the longest prefix fails on cases like catsandog. Another miss is forgetting the empty string returns 0, and that duplicates don't matter. If the DP recurrence slips away under pressure, StealthCoder is the hedge that surfaces it live.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.