Word Break
Understand how to solve the Word Break problem by using dynamic programming methods. Explore how to check if a string can be segmented into a sequence of dictionary words, leveraging memoization and tabulation to optimize solutions efficiently.
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;}}