Word Break Problem

Given a non-empty string s and a list of non-empty words (dictionary), determine if s can be segmented into a space-separated sequence of one or more dictionary words. Formally, check whether there exists a sequence of substrings such that every substring appears in the dictionary.

This problem can be solved by dynamic programming. Define a DP array \(dp\) where \(dp[i]\) is true if the substring \(s[0:i]\) can be segmented; otherwise, it is false. The recurrence relation is given by:

$$dp[i] = \bigvee_{0 \leq j < i} \Big( dp[j] \land \big(s[j:i] \in \text{words}\big) \Big)$$

with the base condition \(dp[0] = true\). The task is to compute \(dp[\text{len}(s)]\) and output True if segmentation is possible, and False otherwise.

inputFormat

The input is given via standard input (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 third line contains \(n\) space-separated words.

outputFormat

Output via standard output (stdout) a single line: True if the string can be segmented into a space-separated sequence of one or more dictionary words; otherwise, output False.

leetcode
2
leet code

True