String Breaker

1. If string 'S' is already present in the dictionary, then you don’t need to break the string and you can print 0 in such cases. 2. If it is impossible to complete the given task, then print -1. 3. All the characters of string 'S' and words inside the Dictionary only contain Uppercased English Alphabets.

The first line of the input contains an integer 'T', denoting the number of test cases. The first line of each test case contains a string 'S', denoting the given string. The second line of each test case contains an integer 'N', denoting the size of the given set of words. The next 'N' lines contain a string denoting the ith word in the dictionary.

For each test case print, the minimum number of times given string 'S' need to be broken in such a way that all the subparts are present in the Dictionary. In cases, when it is impossible to break string S, print -1. Print the output of each testcase in a separate line.

1 <= T <= 50 1 <= N <= 10^4 1 <= |S| <= 50 1 <= |word[i]| <= 50 ‘A’ <= S[i] <= ‘Z’ Where |S| denotes the length of the given string, |word[i]| denotes the length of the ith word in the Dictionary. It is guaranteed that all the words in the dictionary consist of only uppercase English alphabets from ‘A’ to ‘Z’. Time Limit: 1 sec.

Brute Solution

We try to break the given string S, in every possible way and will take the minimum of all ways to break S, such that all the parts are present in the Dictionary.
For trying all possible ways of breaking, we will form a recursive function, which will return the minimum number of breaks required for breaking the given string such that each part is present in the Dictionary.
The base conditions for this will be the following:
- When the string is already present in the Dictionary, we don’t require any breaking in this case hence we return 0 here.
- When string length is 1 and it is not present in the dictionary, so there is no way to break it further as well this is not a part Dictionary, hence we return some big integer denoting there is no possible way to break the given string.
In cases where base conditions are not met, we try to break the string in all possible ways and call the same function to calculate minimum breaks required on both parts.
We keep track of the minimum of all possible ways to break the current string after each attempt of breaking it. And finally, return this minimum.
Calling this function with the current string will give us the required minimum breaks. If it is impossible for the string to break, this will return a big integer value. So we will print -1 in such cases.

Time Complexity

O((K!)*K), where K is the size of the given string.

As we are trying to break each substring at each possible point and redividing those substrings further in next calls, this will make a recursion tree of height K and number of calls to next substrings reduced by 1. Hence overall order of O(K!) operations are done. Also checking at each state whether current substring is part of the Dictionary or not takes O(K) time. Hence, the overall time complexity is O((K!)*K).

Space Complexity

O(K), where K is the size of the given string.

As we are using recursion, so it will take O(K) of stack memory. Hence, the overall space complexity is O(K).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of sample input 1:

Sample Input 2:

Sample Output 2:

Explanation of sample input 2: