Re-Formating

Posted: 7 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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