String Segmentation

You are given a dictionary of n words and a string s. Your task is to determine if the string s can be segmented into a sequence of one or more words from the dictionary.

This problem can be solved using dynamic programming. Define the state \(dp[i]\) to be true if the substring \(s[0:i]\) can be segmented into valid words. The recurrence is given by:

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

Output "yes" if such segmentation exists, otherwise output "no". The answer is case-sensitive.

inputFormat

The input is taken from standard input (stdin) and consists of the following:

1. An integer n on the first line, representing the number of words in the dictionary.
2. A line containing n space-separated words.
3. A line containing the string s which needs to be segmented.

outputFormat

Output a single line with the string "yes" if s can be segmented into one or more dictionary words, or "no" otherwise, printed on standard output (stdout).

5
apple pie pear peach sand
applepiepeach

yes