In order to be irreplaceable, one must always be different
Coco Chanel
Word Break-2
Welcome back, dear reader. So, how is it going? In this article, we will discuss a very interesting problem called WORD BREAK-2. So, what does the problem say?
We will be given some input words and we will be given an input string. We have to make sentences by breaking the string into the words. The words can only be chosen from the list of input words. The output will be the number of sentences that we can make using the words given to us. For instance, have a look at the image shown below:
So, dear reader, we hope that you have understood the question completely. We recommend you refer to this part of the WORDS BREAK-2 VIDEO to understand the question and clear your doubts regarding it if any.
Approach:
Explanation:
We will solve this problem using the conventional Dynamic Programming approach.
Storage and Meaning:
The image below shows the input words given to us and the string that we have to break to make the sentences:
We will make a one-dimensional dp array of the same size as that of the length of the input string. What will each element in that array represent? Have a look at the image given below:
So, each element in the array represents the number of sentences that can be made using the words given to us if the input string is the string till the index that we are at currently.
Direction of solving:
The smallest problem is to make the sentences from a string with only one character and the largest problem is to make the sentences from the entire input string. Therefore, we will solve this problem moving from 0th to the last index of this array.
Travel and Solve:
Let us start solving this problem. Initially, we are at index=0. Since " p " is not a word given in our dictionary, the number of sentences formed will be 0 and we move to the next index.
Now we are at index=1. Dear reader, try to understand the way in which we will break the string from now on. Since we are at index 1, this means that the input string is currently " pe ". Also, this means that we have already visited the index 0 i.e. we already know how many sentences can be generated from the string " p ".
Now we have to check for the string " e " alone and " pe " combined. Why? Think!!! We will discuss this very soon
So, there is no word " e " or " pe " in our dictionary. So, the number of sentences still remains 0 and we move to index 2.
At index=2, we have the string " p " and till index=2, the input string is " pep ". Let us see how we will break this string.
First, let us consider the entire string " pep ". Is this a word in our given dictionary? Yes, it is. So, we can make one sentence if we consider the entire input string. Also, before this, the input strings were " pe " and " p " and there were no sentences that we could form using those two strings.
Hence, there will be only sentence that we can make if the input string is " pep ". So, we will put 1 at dp[2] and move to the next index.
So, we can continue this procedure till index 7. The dp array filled till index 7 is shown in the image below:
Now, let us come to index 8. We have the input string till index 8 as " pepcoding ". The ways in which we will break this string is shown in the image below:
So, what we are doing here is that we start from the first character and take the entire string into consideration and we check whether it is a valid word in our dictionary or not. As we can see, " pepcoding " is a word in our dictionary so, one sentence can be formed using the string " pepcoding ".
Now, it might happen that one of the substrings of this input string is also a valid word.
So, we are going to ignore the first character from the input string now and check for the remaining string i.e. " epcoding ". This is not a valid word.. So, we still have only 1 sentence that we can make from the string " pepcoding ". We will continue this procedure till we reach the string " coding ". The strings that we consider are shown by the lines drawn above the array as shown in the figure below:
Now, the string " coding " is also a valid word. What will be the sentence formed by this string? See (in img-8), when the input string is " coding ", the string before it is " pep ". Both of these are the words in our dictionary.
See, this signifies that the string that we got earlier " pepcoding " itself will form a sentence and the string " coding " will add up to the previous string " pep " to form the sentence " pep-coding ". Hence, till now, we have got two sentences.
Dear reader, we recommend you continue this procedure till we are left with only " g " as the input string and the answer to that will also be 0. So, the answer for this will be 2 as shown in the image below:
So, dear reader, we hope that you have understood this procedure by now. We request you to complete this array on your own now. The completely filled array is shown below:
We recommend you refer to this part of solution video to understand the procedure explained above and clear your doubts regarding the procedure if any.
Note:
Dear reader, we have discussed the problem where we are printing the count of the sentences that we can generate but the question given on the portal is quite easy as compared to this problem. In that question, we just have to print whether we can generate a sentence from the string using the given words or not. If we can, we have to print true else false. So, we can do that using the above method too where if the count of the sentences is greater than 0, we print true and false otherwise. Why? Think!!!!
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
HashSet< String> dictionary = new HashSet< String>();
for (int i = 0; i < n; i++) {
dictionary.add(scn.next());
}
String sentence = scn.next();
System.out.println(solution(sentence, dictionary));
}
public static boolean solution(String sentence, HashSet< String> dictionary) {
boolean[] dp = new boolean[sentence.length() + 1];
dp[0] = true;
for (int i = 1; i < dp.length; i++) {
char ch = sentence.charAt(i - 1);
if (i == 1 && dictionary.contains(ch + "")) {
dp[i] = true;
continue;
}
for (int j = i - 1; j >= 0; j--) {
if (dp[j] == true) {
String strtobechecked = sentence.substring(j, i);
if (dictionary.contains(strtobechecked)) {
dp[i] = true;
}
}
}
}
return dp[dp.length - 1];
}
}
java;
true";
Dear reader, we recommend you refer to the solution video if you have any doubts regarding the code. Now that we have discussed the complete procedure, let us analyze the time and space complexity for the same.
Analysis
Time complexity:
O(n2) where n is the length of the input string
The time complexity for this solution is O(n2) due to the nested loop that we are using to check every previous substring when we are at any particular index.
Space Complexity:
O(n)
The space Complexity is O(n) as we have just made an array of size n where n is the length of the string.
Suggestions:
Here are a few suggestions from our side that you do not want to miss:
We suggest you refer to the solution video once and try to understand the code in depth too as we have discussed the solution to a slightly different yet tougher problem than the problem given on the portal.
We also suggest that you keep revising the previous problems as well and make notes of the problems you face difficulty in. If you want, make notes of every problem you solve as it helps in quick revision of the problems and a lot of deep concepts later. So, keep working hard. Till then, Happy Coding!!!
