Word Break Problem

You are given a non-empty string \( s \) and a list of \( m \) words. Your task is to 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 words \( w_1, w_2, \ldots, w_k \) taken from the given list such that:

\( s = w_1w_2\ldots w_k \)

Use dynamic programming to solve this problem efficiently. One standard recurrence is:

\( dp[i] = \bigvee_{0 \leq j < i} (dp[j] \wedge [s[j:i] \in \text{wordSet}]) \)

where \( dp[i] \) is true if the substring \( s[0:i] \) can be segmented, and \( s[j:i] \) represents the substring of \( s \) from index \( j \) (inclusive) to \( i \) (exclusive).

inputFormat

The input is read from Standard Input (stdin) and consists of three parts:

1. A string \( s \) on the first line.
2. An integer \( m \) on the second line representing the number of words in the dictionary.
3. A line containing \( m \) space-separated words.

outputFormat

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

leetcode
2
leet code

True