Close
Topic list
Word Break II
HARD
15 mins
Strings
Topics (Covered in this problem)
Problem solved
Skill meter
Strings
-
-
Other topics
Problem solved
Skill meter
Matrices (2D Arrays)
-
-
-
-
Sorting
-
-
Binary Search
-
-
Stacks & Queues
-
-
Trees
-
-
Graph
-
-
Dynamic Programming
-
-
Greedy
-
-
Tries
-
-
Arrays
-
-
SQL
-
-
Binary Search Trees
-
-
Heap
-
-
Bit Manipulation
-
-
Solve problems & track your progress
Checkout your overall progress in every topic here
Become
Sensei
in DSA topics
Open the topic and solve more problems associated with it to improve your skills
Check out the skill meter for every topic
See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

# Word Break II

Contributed by
Vishal Modani
Hard
0/120
Avg time to solve 15 mins
Success Rate 85 %
Share

## Problem Statement

#### Note :

``````The same word in the dictionary can be used multiple times to make sentences.
Assume that the dictionary does not contain duplicate words.
``````
Detailed explanation ( Input/output format, Notes, Constraints, Images )
##### Sample Input 1:
``````1
6
god is now no where here
godisnowherenowhere
``````
##### Sample Output 1:
``````god is no where no where
god is no where now here
god is now here no where
god is now here now here
``````
##### Explanation to Sample Input 1:
``````One way to make sentences is to take “god” and append a space, then take “is”  and append space, take “now” from the dictionary and take “here” as well.
Similarly, for other sentences also, we can add space to get other possible sentences. Note that we can reuse dictionary words as “no” and “now” are used two times in the same sentence.
``````
##### Sample Input 2:
``````1
4
god is no here
godisnowhere
``````
##### Sample Output 2:
``````No output to be printed
``````
##### Explanation to Sample Input 2:
``````We can not make any sentence because after making “god is no” we will be stuck with “where”. There is no way to break “where” further such that we can get any word from the dictionary.
``````
Auto
Console