Minimum Spaces for Word Segmentation

You are given a string text without spaces and a dictionary containing a list of valid words. Your task is to determine the minimum number of spaces that need to be inserted into the string so that every segmented word is present in the dictionary.

If it is not possible to segment the string using the provided dictionary, output -1.

More formally, given a string \(S\) and a set of words \(D\), find the minimum number of spaces \(k\) such that \(S = w_1 w_2 \ldots w_{k+1}\) where each \(w_i\) is in \(D\). If no such segmentation exists, return \(-1\).

inputFormat

The input is given via standard input (stdin) and has the following format:

1. An integer n on the first line representing the length of the text string.
2. A string text on the next line without any spaces.
3. An integer m on the next line representing the number of words in the dictionary.
4. m subsequent lines each containing a valid word (without spaces).

outputFormat

Output a single integer to standard output (stdout), which is the minimum number of spaces required to segment the string into valid dictionary words. If it is impossible to segment the string, output -1.

13
applepenapple
4
apple
pen
penapple
applepen

1