String Segmentation

You are given a string s and a list of words forming a dictionary. Your task is to determine whether the string s can be segmented into a space-separated sequence of one or more dictionary words.

In other words, decide if there exists a sequence of indices 0 = i₀ < i₁ < ... < i_k = |s| such that every substring s[i_j:i_j+1] (for 0 ≤ j < k) is a word in the given list. This can be formalized using the following dynamic programming recurrence:

\( dp[i] = \begin{cases} \text{True} & \text{if } \exists\, j < i \text{ such that } dp[j] \text{ is True and } s[j:i] \in \text{wordDict} \\ \text{False} & \text{otherwise} \end{cases} \)

An empty string is always considered segmentable.

inputFormat

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

• The first line contains the string s.
• The second line contains an integer n representing the number of words in the dictionary.
• The third line contains n words separated by spaces. If n is zero, the third line may be empty.

outputFormat

Print to standard output (stdout) a single line: "True" if the string can be segmented into one or more dictionary words; otherwise, print "False".

leetcode
2
leet code

True