Word Break Problem

Given a non-empty string \(s\) and a dictionary of words \(W\), determine whether \(s\) can be segmented into a sequence of one or more words from \(W\). More formally, define a boolean array \(dp[0 \ldots |s|]\) such that \(dp[0] = true\) and for each \(1 \le i \le |s|\), \(dp[i] = true\) if there exists a \(j\) with \(0 \le j < i\) satisfying \(dp[j] = true\) and \(s[j:i] \in W\). Output Yes if such a segmentation exists, otherwise output No.

inputFormat

Input is read from standard input (stdin). The first line contains the string s. The second line contains an integer n indicating the number of words in the dictionary. The following n lines each contain one word belonging to the dictionary.

outputFormat

Output a single line to standard output (stdout): Yes if the string s can be segmented into a sequence of dictionary words, or No otherwise.

applepenapple
2
apple
pen

Yes