Word Break Problem

You are given a non-empty string s and a dictionary containing a list of non-empty words. Your task is to determine whether s can be segmented into a space-separated sequence of one or more dictionary words.

More formally, given a string \( s \) and a set of words \( \text{wordDict} \), check if \( s \) can be segmented as:

[ s = w_1 + w_2 + \cdots + w_k, \quad \text{where } w_i \in \text{wordDict} \text{ for } 1 \le i \le k, ]

For example:

• s = "leetcode" and wordDict = ["leet", "code"] should return True because "leetcode" = "leet" + "code".
• s = "applepenapple" and wordDict = ["apple", "pen"] returns True.
• s = "catsandog" and wordDict = ["cats", "dog", "sand", "and", "cat"] returns False.

This problem can be solved using dynamic programming.

inputFormat

The input is received from stdin and has the following format:

Line 1: A string s representing the string to segment.
Line 2: An integer n representing the number of words in the dictionary.
Next n lines: Each line contains a single word which is part of the dictionary.

outputFormat

Output a single line to stdout containing either True or False (case-sensitive) indicating whether the string s can be segmented into one or more words found in the dictionary.

## sample

leetcode
2
leet
code

True

</p>