Word Break Problem

Given a string s and a dictionary of words, determine whether s can be segmented into a sequence of one or more dictionary words. In other words, check if there exists a space‐separated sequence of dictionary words that concatenates to form s.

The problem can be expressed in the following latex formulation:

$$dp[i] = \bigvee_{0 \le j < i} \left\{ dp[j] \land \left(s[j:i] \in D\right) \right\}$$

with the initial condition $$dp[0] = true$$. The answer is YES if dp[N] is true (where N denotes the length of s), and NO otherwise.

inputFormat

The input is given via stdin and consists of multiple lines:

• The first line contains the string s.
• The second line contains an integer n, which is the number of words in the dictionary.
• The following n lines each contain a single word from the dictionary.

outputFormat

Output a single line to stdout: YES if the string s can be segmented into a sequence of one or more dictionary words; otherwise, output NO.

leetcodeable
2
leet
code

NO