Word Break II

Try to solve the Word Break II problem.

We'll cover the following

Statement#

You are given a string, s, and an array of strings, word_dict, representing a dictionary. Your task is to add spaces to s to break it up into a sequence of valid words from word_dict. We are required to return an array of all possible sequences of words (sentences). The order in which the sentences are listed is not significant.

Note: The same dictionary word may be reused multiple times in the segmentation.

Constraints:

  • 1≤1 \leq s.length ≤20\leq 20

  • 1≤1 \leq word_dict.length ≤1000\leq 1000

  • 1≤1 \leq word_dict[i].length ≤10\leq 10

  • s and word_dict[i] consist of only lowercase English letters.

  • All the strings of word_dict are unique.

Examples#

canvasAnimation-image

1 of 2

canvasAnimation-image

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Word Break II

1

What is the output if the following input string and dictionary are provided as input?

s = “pineapplepenapple”

word_dict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]

A)

[“pine apple pen apple”, “pineapple pen apple”, “pine applepen apple”]

B)

[“pine apple pen apple”, “pine applepen apple”]

C)

[“pineapple pen apple”]

D)

[]

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Create a 2D table where each entry corresponds to a prefix of the input string and store an array of all possible sentences that can be formed using that substring.

Iterate over all prefixes of the input string.

For each prefix, iterate over its suffixes and check whether the suffix is a valid word in the dictionary.

If the suffix is a valid word, combine it with all possible sentences that can be formed using the prefix to the left of it.

Store the array of all possible sentences that can be formed using the current prefix in the corresponding entry of the table.

After processing all prefixes of the input string, return the list of all possible sentences that can be formed using the complete string.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 ag node_11 al node_21 icl node_31 mag node_41 magic node_51 ly node_61 lly
Visualization for Input #2
Word Break II

Solution: Counting Bits

Solution: Word Break II