262. Word Break II (Count of Segmentations)

HardStringString

Given a string s and a dictionary of words, return the number of distinct ways s can be segmented into a sequence of dictionary words (words may be reused). Input: JSON {s, words}.

Input: JSON {s, words}.

Output: Integer — number of segmentations.

Examples

Example 1 
Input: {"s":"catsanddog","words":["cat","cats","and","sand","dog"]}
Output: 2
Explanation: 'cats and dog' and 'cat sand dog'.
Example 2 
Input: {"s":"pineapplepenapple","words":["apple","pen","applepen","pine","pineapple"]}
Output: 3
Explanation: Three segmentations.
Example 3 
Input: {"s":"catsandog","words":["cats","dog","sand","and","cat"]}
Output: 0
Explanation: No valid segmentation.

Constraints

Asked by

BloombergAmazonOracleMetaGoogleMicrosoft
Solve this problem in the editor →