# Word Break - I #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given n space separated strings, which represents a dictionary of words.2. You are given another string which represents a sentence.3. You have to print all possible sentences from the string, such that words of the sentence are      present in dictionary.Note -> Check out the question video and write the recursive code as it is intended without                changing signature. The judge can't force you but intends you to teach a concept.`
Input Format
`A number n n strings representing wordsa string representing a sentence`
Output Format
`Check the sample ouput and question video.`
Question Video
Constraints
`1 <= number of words <= 101 <= length of each word <= 151 <= length of sentence <= 1000`
Sample Input
`11i like pep coding pepper eating mango man go in pepcodingilikepeppereatingmangoinpepcoding`
Sample Output
`i like pepper eating man go in pep coding i like pepper eating man go in pepcoding i like pepper eating mango in pep coding i like pepper eating mango in pepcoding `

• Editorial

We will solve this question with the recursion. We will first store all the given words in a set. Then we will generate all the prefixes of the current word. If the prefix is present in the set, we will call the recursive function for the remaining string. When the length of the string is zero, we will print the ans and return.

Signature -

public static void wordBreak(String str, String ans, HashSet < String > dict)

str  = Input string

ans = answer till the current level

dict = Set containing all the given words

Code -

```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 false

Code Explained -

With the help of for loop, we generate all the prefixes. If the prefix is present in the dict, we first find the suffix left and call the recursive function for the remaining string. We also append the prefix to the ans.

Base Case -

When the length of the str is zero, it means we have used the whole string. We will print the ans and return.

• Related Topics

Run

Run
Id Name