Word Break

Given a non-empty string \(s\) and a list of non-empty words forming a dictionary, determine whether \(s\) can be segmented into a space-separated sequence of one or more dictionary words. In other words, check if there exists a sequence of indices \(0 = i_0 < i_1 < \cdots < i_k = |s|\) such that every substring \(s[i_{j-1}:i_j]\) is a valid word in the dictionary.

The typical approach is to use dynamic programming, where we maintain an array \(dp\) such that \(dp[i]\) is true if the substring \(s[0:i]\) can be segmented into dictionary words. The recurrence is given by:

[ dp[i] = \bigvee_{0 \leq j < i} \left(dp[j] \land \bigl(s[j:i] \in D\bigr)\right) ]

where \(D\) is the set of dictionary words. The answer is \(dp[|s|]\).

inputFormat

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

• The first line contains a non-empty string s which needs to be segmented.
• The second line contains an integer n representing the number of words in the dictionary.
• The next n lines each contain one word from the dictionary.

outputFormat

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

leetcode
2
leet
code

True