Redirecting to
NADOS


  Prev   Next

Word break-1







Programming isn't about what you know; it's about what you can figure out

Word break-1

Welcome back, dear reader. So, how is it going? Hope you are challenging yourself with a variety of problems in this course. So, this problem is called WORD BREAK-1. What does this problem say? Have a look at the image shown below:

img

Important Link : Problem Link, Solution Video Link

Understanding the problem

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. For example in the above image, the string had 4 possible sentences because of the input words that were given. You cannot reverse the string or change the order of words in the string in any way. The string will be in the same sequence. We can just break it into different words. You may refer to the WORDS BREAK-1 VIDEO to understand the question completely if you have any doubts regarding it. We recommend you try to solve the problem yourself first and then move to the solution.

Approach

Time Complexity: O(2^n ) where n is the length of the input string to be broken into the sentences

Space Complexity: O(h) where h is the height of the recursion stack if we consider the recursion space and O(1) otherwise.

Algorithm:

  1. We will keep on extracting a substring from as a prefix and if the substring that we have extracted does not exist, we will try to extract the furthersubstring. For instance:We kept on checking for the prefix and when we got a prefix substringwhich is present in the dictionary, we extracted it.
    img
  2. After extracting one word, we will store it in the answer so far and we willmove forward and try to extract another word from the remaining string.
  3. When the question string becomes empty, print the answer and return.

Explanation:

Let us analyze the solution with the help of a tree diagram. After we analyze andunderstand this procedure completely, the coding part will be a piece of cake foryou.

Let us take our above example only. So, we have an input string "microsofthiring".We also have a set of words: micro, soft, microsoft, hi, ring, hiring. Let us try to break the input string into the sentences.

We will start from the left of the string and try to find a substring which is present in the dictionary i.e. the set of words that we are given as the inputy. If we find such a substring, the question string will be the remaining substring and the answer string will be updated to contain the extracted substring also.

img

you can see from the diagram above, we have selected the word "micro" as it was a part of the dictionary and we got the remaining question as "softhiring" and when we select the word "microsoft", we get the word "hiring" as the remaining question.

So, we know how recursion works, right? We have shown the two calls above simultaneously but we know that only the left call will be initiated first. So, let us do that now. We select the word "micro" and a recursive call is made with the question string being "softhiring" and the answer so far being "micro".

img

Now the question string is "softhiring" and we can separate only one substring i.e."soft" from it as it is the only substring which is present in the dictionary. So, the question string will now be "hiring" and the answer fo far is "micro soft". (Wecan't depict space in the diagram properly hence we have kept a hyphen after every word hence there is a hyphen between micro and soft indicating they are different words in img-5.)

img

After this, we can either take out the substring "hi" or the entire string "hiring". Again, only one call is made at a time. So, we take "hi" and we are left with the question string "ring".

img

Now, we only have "ring" left in the question string and it is a part of the dictionary. So, we can remove it. The question string will be empty and the answer so far will contain one complete sentence.

Base Case: This is also the base case of recursion. Here, we will print the answer string and return from the recursion. So, whenever the question string becomes empty, print the answer and return.

img

So, we will return from there and get back to the previous level in the recursion stack. Does this problem look familiar to you? It is just like all the problems that we did in the RECURSION ON THE WAY UP SECTION in the foundation course. If you have solved those problems then this problem is not much of a big issue for you.

So, we hope that you have now understood the procedure that we are going to follow. We recommend you continue this procedure and generate the entire tree. The complete tree is given below for your reference:

img

We recommend you watch the solution video to understand the complete procedure shown above.

Now that we have understood the complete procedure, let us go to the code:

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> dict = new HashSet<>(); for(int i = 0 ; i < n; i++){ dict.add(scn.next()); } String sentence = scn.next(); wordBreak(sentence,"", dict); } public static void wordBreak(String str, String ans, HashSet<String> dict){ if(str.length() == 0){ System.out.println(ans); return; } for(int i = 0; i < str.length(); i++){ String left = str.substring(0, i + 1); if(dict.contains(left)){ String right = str.substring(i + 1); wordBreak(right, ans + left + " ", dict); } } } }
java; true";

We hope that you have got the entire procedure and have also understood the code above. If you have any doubts regarding the code, we suggest you refer to the solution video to understand the code above and clear all your doubts. Let us now discuss the time and space complexity of the above method/code.

Analysis
Time Complexity

So, can you guess the time complexity of this code? Did you solve the problem PALINDROMIC PARTITIONS ? We recommend you solve this problem also and try to understand the relation between the time complexity of these two problems. So, it was a hint for you to find the time complexity. What is it? Yes, it is O(2 n ). Why? Let's analyze it.

Best Case:O(n)
Let's see the best case complexity of this problem. Consider that you are not able to break the string into any words that match the dictionary. This means that you have traversed the string once and you looked for all the prefix substrings (the word prefix is really important here as we are not looking for a substring from the middle of the string.)and you were not able to find a word which matches the dictionary. So, the time complexity is just O(n) as you traversed the string once.

Worst Case:O(2^n)
The number of recursion calls depends upon the number of words that we are able to break the given string into. Let us say we have such a situation that every character of the string is a word in the dictionary. For example:

img
In this case, the string can be broken into n parts i.e. n-1 partitions are done. This means that n-1 recursive calls are performed. In each recursive call, each word has 2 choices, to be selected into the answer so far or not to be. So, the time complexity for n-1 recursive calls will become 2 n-1 . So, we can say that the time complexity is O(2 n ).

Average Case:O(2^n)
The average case is the same as the base case and hence the time complexity of this solution is O(2 n ).

Space Complexity

The space complexity is O(h) where h is the height of the recursion stack considering the recursion space. If you want a little bit more detail on the space complexity, refer to the PALINDROMIC PARTITIONS ARTICLE where we have discussed the space complexity a little bit more.

So, dear reader, we hope that you have understood the time and space complexity analysis also. If you have any doubts regarding the procedure or the code, we suggest you refer to the complete solution video to clear all your doubts. With this, we have completed this problem.

Suggestions:

Here are some suggestions from our side that you do not want to miss:

  1. We suggest you revisit the RECURSION ON THE WAY UP SECTION once so that your revision also goes on simultaneously and you will be able to solve the problems related to this section very easily if they come up again.
  2. A general advice, take some rest in between also. Do not over stress yourself. Just keep your mind relaxed and code with your full minded presence and not when you are feeling retarded. This will help in increasing your productivity. So, keep practicing and taking small breaks. Till then, Happy Coding!!!
word break 1
Author: Guneet Malhotra
 
Run
Id Name