Word Break Problem

Given a non-empty string \( s \) and a dictionary of words, determine if \( s \) can be segmented into a space-separated sequence of one or more dictionary words. For example, if \( s = \texttt{applepenapple} \) and the dictionary is \( [\texttt{apple}, \texttt{pen}] \), then the output should be True because the string can be segmented as \( \texttt{apple pen apple} \).

The problem requires you to use an efficient algorithm (e.g., dynamic programming) so that even larger strings can be processed quickly.

inputFormat

The input is taken from standard input (stdin) and consists of multiple lines:

• The first line contains the string \( s \) that needs to be segmented.
• The second line contains an integer \( n \) which is the number of words in the dictionary.
• Each of the next \( n \) lines contains one word from the dictionary.

outputFormat

Output to standard output (stdout) a single line. Print True if the string can be segmented into a sequence of one or more dictionary words, otherwise print False. The output is case-sensitive.

applepenapple
2
apple
pen

True