Re-Formating

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in company
Amazon

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
marginissmall
6
small all mall is in margin
abcd
10
a b c d e f g h i j
Sample Output 1 :
2
3

Explanation For Sample Input 1 :

For the first test case S can be written as S = ”margin is small”

For the second test case S can be written as S = “a b c d”
Sample Input 2 :
2
aaaaaaaa
1
a
codeninjacodeninja
3
code ninja codeninja
Sample Output 2 :
7
1
Hint

Can we use recursion to solve this problem? 

Approaches (3)
Recursive

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.

Time Complexity

O(2 ^ N) where N is the size of S,

 

Each prefix may be present in DRR, so we have to recursively solve each suffix. It takes O (2 ^ N) time.

Space Complexity

O(N), where N is the size of S.

 

The space complexity due to the recursive stack will be O(N)..

Code Solution
(100% EXP penalty)
Re-Formating
Full screen
Console