Word Break Problem

You are given a string s and a dictionary of words wordDict. Your task is to determine whether the string s can be segmented into a space-separated sequence of one or more dictionary words. In other words, you must decide if there exists a sequence of words w1, w2, ..., wk from wordDict such that s = w1 + w2 + ... + wk.

The problem can be formalized using dynamic programming as follows:

$$dp[i] = \begin{cases} true, & \text{if } s[0:i] \text{ can be segmented into words from } wordDict,\\ false, & \text{otherwise.} \end{cases}$$

If the entire string can be segmented, output YES; otherwise, output NO.

inputFormat

The input is given from standard input (stdin) in the following format:

• The first line contains the string s.
• The second line contains an integer n, representing the number of words in the dictionary.
• Each of the following n lines contains a single word that belongs to the dictionary.

outputFormat

Output a single line to standard output (stdout) containing YES if the string can be segmented into a sequence of dictionary words, or NO otherwise.

## sample

leetcode
2
leet
code

YES

</p>