Word Break Problem

You are given a string s and a dictionary of words wordDict. The task is to determine whether s can be segmented into a space-separated sequence of one or more dictionary words. Formally, you need to decide if there exists a way to split s as

$$s = s_1 s_2 \ldots s_k, \quad k \ge 1$$

such that every segment \( s_i \) is in wordDict.

Note that an empty string is considered to be segmented successfully.

Example:

• Input: s = "leetcode", wordDict = ["leet", "code"]
• Output: True

Your program must read the input from standard input and write the answer to standard output.

inputFormat

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

• The first line contains the non-negative string s. (It can be empty.)
• The second line contains an integer n representing the number of words in the dictionary.
• The following n lines each contain a word from the dictionary.

For example:

leetcode
2
leet
code

outputFormat

Output a single line containing either True or False indicating whether the string can be segmented into dictionary words.

For example:

True

## sample

leetcode
2
leet
code

True