Word Break Problem

You are given a non‐empty string s and a list of non‐empty words. Determine if s can be segmented into a space-separated sequence of one or more dictionary words. Formally, you need to decide whether there exists a sequence of words \(w_1, w_2, \ldots, w_k\) (each \(w_i\) is in the dictionary) such that:

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

The segmentation may reuse words from the dictionary. The input is given via standard input and the result should be printed to standard output as either True or False. An empty string is considered to be segmented (i.e. returns True).

inputFormat

The input is read from standard input (stdin) and formatted as follows:

• 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 word from the dictionary.

outputFormat

Output a single line to standard output (stdout) with either True if the string can be segmented into one or more dictionary words, or False otherwise.

applepenapple
2
apple
pen

True