String Segmentation Problem

You are given a string s and a list of words. Your task is to determine whether the string s can be segmented into one or more words that exist in the provided word list. Formally, let \(dp[i]\) be a boolean value indicating whether the substring \(s[0\ldots i-1]\) can be segmented into words from the list. The recurrence relation for the dynamic programming solution is given by:

\[ dp[i] = \bigvee_{0 \leq j < i} \Big( dp[j] \wedge (s[j\ldots i-1] \in \text{wordList}) \Big) \]

The answer should be YES if the string can be segmented, and NO otherwise. Note that an empty string is considered to be segmentable.

inputFormat

The input is provided via standard input (stdin) and has the following format:

• The first line contains the string s.
• The second line contains an integer n — the number of words in the word list.
• The following n lines each contain a word from the word list.

outputFormat

Output a single line via standard output (stdout) containing YES if the string s can be segmented into words from the list, or NO otherwise.

applepie
3
apple
pie
orange

YES