Word Break Problem

You are given a string s and a dictionary of 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} \), determine if there exists a sequence of indices \( 0 = i_0 < i_1 < \dots < i_k = |s| \) such that for every \( j \) with \( 0 \le j < k \), the substring \( s[i_j:i_{j+1}] \) is in \( \text{wordDict} \). This can be expressed using dynamic programming as:

[ dp[i] = \bigvee_{j=0}^{i-1} \Big( dp[j] \land \mathbf{1}(s[j:i] \in \text{wordDict}) \Big), \quad 0 \le i \le |s| ]

The answer is True if \( dp[|s|] \) is true and False otherwise.

inputFormat

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

1. The first line contains the string s.
2. The second line contains an integer n, the number of words in the dictionary.
3. The following n lines each contain a dictionary word.

Note: s can be an empty string.

outputFormat

Output a single line to stdout containing either True or False indicating whether the string s can be segmented into a sequence of one or more dictionary words.

leetcode
2
leet
code

True