Redirecting to
NADOS

Word Break - I

  Prev   Next

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 words
a string representing a sentence
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= number of words <= 10
1 <= length of each word <= 15
1 <= length of sentence <= 1000
Sample Input 
11
i like pep coding pepper eating mango man go in pepcoding
ilikepeppereatingmangoinpepcoding
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.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name