Word Break Problem

Given a non-empty string \(s\) and a list of non-empty dictionary words, determine if \(s\) can be segmented into a space-separated sequence of one or more dictionary words. That is, check whether there exists a segmentation \(s = w_1w_2\ldots w_k\) such that each \(w_i\) is present in the dictionary.

For example, if \(s = "leetcode"\) and the dictionary is \(["leet", "code"]\), then the answer is True because \(s\) can be segmented as "leet code".

inputFormat

Input is provided via standard input (stdin). The first line contains the string (s). The second line contains an integer (n) representing the number of words in the dictionary. The following (n) lines each contain one dictionary word.

outputFormat

Output a single line to standard output (stdout): print "True" if the string can be segmented into a sequence of one or more dictionary words, and "False" otherwise.## sample

leetcode
5
leet
code
le
et
c

True