Word Break
Explore how to apply dynamic programming to verify whether a given string can be segmented into one or more dictionary words. Understand constraints, problem setup, and build solutions through memoization and tabulation strategies in this lesson.
We'll cover the following...
Statement
Given a string, s, and a dictionary of strings, wordDict, check if s can be segmented into a space-separated sequence of one or more dictionary words. If yes, return TRUE; else, return FALSE.
Note: The same word in the dictionary may be used multiple times.
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:
Can the string “pineapplepenapple” be split into sequences separated by spaces using the following words from the dictionary?
[“apple”, “pen”, “applepen”, “pine”, “pineapple”]
Yes
No
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.*;public class Main{public static boolean wordBreak (String s, List<String> wordDict ) {// Replace this placeholder return statement with your codereturn false;}}