Word Break Problem

Given a string \( s \) and a dictionary of words \( D \), determine if \( s \) can be segmented into a space-separated sequence of one or more dictionary words. Formally, you need to check whether there exists a sequence of indices \( 0 = i_0 < i_1 < \cdots < i_k = n \) such that each substring \( s[i_{j-1} : i_j] \) (for \( 1 \leq j \leq k \)) is in \( D \).

For example, given \( s = \texttt{applepie} \) and \( D = \{\texttt{apple}, \texttt{pie}\} \), the answer is True because \( s \) can be segmented as \( \texttt{apple pie} \). Conversely, if \( D = \{\texttt{apple}, \texttt{pea}\} \), the answer is False since no valid segmentation exists.

inputFormat

The input consists of two lines:

1. The first line contains a string \( s \). This string may be empty.
2. The second line contains a list of dictionary words separated by spaces.

Note: All inputs are read from standard input (stdin).

outputFormat

Output a single line containing True if the string \( s \) can be segmented into a sequence of one or more dictionary words, and False otherwise. The output is printed to standard output (stdout).

applepie
apple pie

True