Dynamic ProgrammingStringHash Set
Given a string and a dictionary of words, decide whether the string can be split into a sequence of dictionary words. Dictionary words may be reused any number of times.
Input
Line 1: the string s. Line 2: m, the number of dictionary words. Line 3: the m words.
Output
Print true if s can be segmented, otherwise false.
Constraints
1 <= length of s <= 300 1 <= m <= 20 1 <= length of each word <= 20
Example 1
Input
leetcode 2 leet code
Output
true
leet + code.
Example 2
Input
catsandog 5 cats dog sand and cat
Output
false
No combination covers the trailing og.