Word Break II
Explore how to use dynamic programming to break a string into all possible sequences of valid dictionary words. Understand memoization and tabulation to optimize solutions for complex string segmentation problems.
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:
import java.util.*;class Main {public static List<String> wordBreak(String s, List<String> WordDict) {// Replace this placeholder return statement with your codereturn new ArrayList<String>();}}