Word Break II
Explore how to apply dynamic programming to segment a string into valid words from a given dictionary. Learn to generate all possible sentences by efficiently combining words through memoization and recursion. This lesson helps you implement Word Break II solutions in Go by understanding problem constraints and leveraging design patterns.
We'll cover the following...
Statement
You are given a string, s, and an array of strings, wordDict, representing a dictionary. Your task is to add spaces to s to break it up into a sequence of valid words from wordDict. 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 -
wordDict.length -
wordDict[i].length -
sandwordDict[i]consist of only lowercase English letters. -
All the strings of
wordDictare 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.
package mainfunc wordBreak(s string, wordDict []string) []string {// Replace this placeholder return statement with your codereturn make([]string, 0)}