String Breaker
Last Updated: 15 Jan, 2021
Difficulty: Easy
You are given a string ‘S’ and a set of words named ‘Dictionary’. You can perform the operation of breaking the given string 'S', in any possible way and divide the given string into any number of subparts. Your task is to break the given string 'S', such that all the subparts are present in the Dictionary. You just need to tell the minimum number of times you need to break the string 'S' in order to accomplish the above task.
Note:
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.
Input format:
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.
Output format:
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.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
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.
Approach 1
- 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.
Approach 2
- 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.
- One thing to observe here is that the same substring from multiple ways, such as we can reach substring S[2:K-1] both from S[1:K-1] and S[2, K], where K is the length of the given string S. This is leading to recomputation for the same substring again and again.
- Hence in order to get rid of this recomputation, we can store the results for each state in a table and use the computed results.
- 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.
SIMILAR PROBLEMS
Divisible Substrings
Posted: 29 Jul, 2022
Difficulty: Easy
Ninja and Numbers
Posted: 30 Jul, 2022
Difficulty: Moderate
Longest Palindromic Substring
Posted: 4 Sep, 2022
Difficulty: Moderate
Cakes
Posted: 23 Sep, 2022
Difficulty: Easy
1-3 Palindrome
Posted: 4 Oct, 2022
Difficulty: Easy
