Word Break II
Explore dynamic programming techniques to break a string into all possible sequences of valid words from a given dictionary. This lesson helps you understand problem constraints, practice solutions, and implement efficient algorithms for Word Break II.
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:
-
s.length -
word_dict.length -
word_dict[i].length -
sandword_dict[i]consist of only lowercase English letters. -
All the strings of
word_dictare unique.
Examples
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
What is the output if the following input string and dictionary are provided as input?
s = “pineapplepenapple”
word_dict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
[“pine apple pen apple”, “pineapple pen apple”, “pine applepen apple”]
[“pine apple pen apple”, “pine applepen apple”]
[“pineapple pen apple”]
[]
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.
Try it yourself
Implement your solution in the following coding playground.
def word_break(s, word_dict):# Replace this placeholder return statement with your codereturn []