Word Break Problem

Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. In other words, check if there exists a sequence of words w₁, w₂, ..., w_k such that:

\( s = w_1 + w_2 + \cdots + w_k \)

where each wi is in wordDict. Note that when s is an empty string, it is considered segmented (i.e. returns True).

inputFormat

The input is read from stdin and consists of multiple lines:

1. The first line contains a non-negative string s consisting of lowercase letters. (It may be empty.)
2. The second line contains an integer n which represents the number of words in the dictionary.
3. The following n lines each contain a non-empty word representing an element of wordDict.

outputFormat

Output a single line to stdout containing either True if the string s can be segmented into a sequence of dictionary words, or False otherwise.

applepenapple
2
apple
pen

True