Re-Formating

PROBLEM STATEMENT

You are given a string S and a dictionary of words DRR of length ‘M’. It is guaranteed that S does not contain any space. DRR is a list of words.

Your task is to convert S into a document of space-separated words such that each word is present in the dictionary DRR, and the number of spaces in between the word is minimized. You have to print the minimum number of spaces used.

For example :

S = ”iamalice”, DRR = [“i”, “am”, “alice”, “iam”] 

Here the answer is 1, as S  can be returned as “iam alice” which uses only 1 space. S = ”i am alice” is also valid but it uses 2 spaces.

Input Format :

The first line of input contains an integer T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains the string S.

The second line of each test case contains ‘M’, the length of the dictionary DRR.

The third line of each test case contains ‘M’ space-separated words denoting the elements of the array/list DRR.

Output Format :

For each test case print the minimum number of spaces used to convert S to a Document for which each word is present in DRR. 

If there is no way to convert S into a document them print -1.

Output for each test case is printed in a separate line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 1000
1 <= M <= 10^4
1 <= length of DRR[i] <= 20      

Time Limit: 1 sec

Approach 1

We will go through S from left to right and check if the current string is present in DRR or not. And call the recursion function for the remaining suffix of S and pick the best answer out of them.

The algorithm will be-

If S is empty return -1
We will maintain a variable BEST, for the final result.
We will iterate through all PREFIX of S from left to right
- If PREFIX is present in DRR
  - BEST = min(BEST, 1 + solve(S - PREFIX))
Return BEST

Here PREFIX is the current prefix of S, and S - PREFIX is the string S remaining after removal of the prefix from S.

Try Problem

Approach 2

We will iterate over prefix and using hashing check whether it is present in DRR or not. And call the recursion function for the remaining suffix of S and pick the best answer out of them. After computing the best answer for a suffix we will memorize it.

Polynomial hashing: Link

The algorithm will be-

Hash all the strings in DRR and store them in a set.
If the answer for the current suffix is computed return it.
We will maintain a variable BEST, for the final result.
We will iterate through all PREFIX of S from left to right
- If PREFIX is present in DRR
  - BEST = min(BEST, 1 + solve(S - PREFIX))
Store the answer for the current suffix.
Return BEST

Here PREFIX is the current prefix of S, and S - PREFIX is the string S remaining after removal of the prefix from S.

Try Problem

Approach 3

We will maintain an array DP to store the answer for a suffix.

Iterate over all the suffixes of string S from right to left and then for each suffix iterate over all of its prefixes. And using hashing check if it is in DRR.

Polynomial hashing: Link

The algorithm will be-

Hash all the strings in DRR and store them in a SET.
Create an array/list DP to store the answer for suffixes
Iterate over a SUFFIX of S.
- For all PREFIX of SUFFIX
  - If PREFIX in DRR
    - DP[SUFFIX] = min (DP[SUFFIX], 1 + DP[SUFFIX - PREFIX] )
Return DP[0]

Try Problem