Last Updated: 23 Sep, 2020

Word Break-1

Hard

Asked in companies

Solve now

Problem statement

You are given a string 's', and a dictionary of words 'dict' containing 'n' words. Your task is to add spaces in 's' to form valid sentences, where each word is a word from the dictionary.

You need to return all possible sentences that can be formed using the given dictionary.

Note :

The same word from a dictionary can be used as many times as possible to make sentences.

Input format :

The first line contains an integer value ‘n’ which denotes the size of the dictionary.
Next ‘n’ lines contains a non-empty string denoting words of dictionary.
Next (n+1)th line contains a non-empty string 's'.

Output format :

The output contains each possible sentence on a new line. If no such string can be formed then output is '-1'.

Note :

You don’t need to print anything. Just implement the given function.

Solve now

Approaches

01 Approach

We need to keep exploring the given string from current position ‘i’ to until we wouldn’t find a position such that substring ‘i’ to ‘j’ exists in the dictionary.

The algorithm looks like:

Store all words of the dictionary in unordered_map to speed up checking whether a current word exists in the dictionary or not?
If sentence size is ended then just return with a null string of list.
Else,
1. You start exploring every substring from the start of the string and check if it is in the dictionary.
  1. If it is
    1. Then you check if it is possible to form the rest of the sentence using dictionary words. If yes, you append the current substring to all the substring possible from the rest of the sentences.
2. If none of the substrings of sentences are present in the dictionary, then there are no sentences possible from the current string.

Solve now

02 Approach

While exploring all possibilities, we are also going to store whatever solution we got till now for a sentence so that we will be able to avoid redundant function calls.

Algorithm Looks Like:

Let’s say

unordered_map<int,vector<string>> dp

dp[index] contains a list of all the valid sentences that can be formed with a substring of the sentence from “index” to “sentence.size()-1”.

Before calling the recursive function for any “index” of sentences, we should check whether we have any solution for that or not?
1. If we have already a solution for current “index” in “dp” then simply return the solution corresponds to the current “index”,
Else we will solve the problem.
1. You start exploring every substring from the “index” of the string till the end and check if it is in the dictionary.
  1. If it is
    1. Then you check if it is possible to form the rest of the sentence using dictionary words. If yes, you append the current “word” to all the substrings which are possible to make the rest of the sentences.
2. If none of the substrings of sentences is present in the dictionary, then there are no sentences possible from the current “index”.
And finally, before returning the answer, we will save it in “dp” for later use.

Solve now

03 Approach

The idea is to use Trie data structure.

A trie is a tree-like data structure whose nodes store the letters of an alphabet. By structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree.

Using trie will help us to save time and space.

Algorithm:

Generate a trie by adding the words of the dictionary. The last letter of each word should be marked as the terminal or end of the word.
After trie is built, string ‘S’ can be easily compared letter by letter in the trie.
Traverse the string ‘S’ from left to right:
- If the current character is not present as the children of the root of the trie, return from here as we can’t break the given string in valid words.
- If at any point, we encounter a leaf in the trie, we can assume that we have found a valid word in the dictionary.
  - If we reach the end of the string ‘S’, we will add the sentence formed by breaking the string ‘S’ to our output array.
  - Else, recursively try to break the remaining string.
Return the output array containing all the possible sentences obtained from breaking the given string ‘S’.

Solve now