Word Break
Explore how to solve the Word Break problem by applying dynamic programming. Understand how to check if a string can be segmented into valid dictionary words and practice implementing an efficient solution that handles multiple uses of dictionary entries. Gain skills essential for tackling similar coding interview challenges.
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.
function wordBreak(s, wordDict){// Replace this placeholder return statement with your codereturn false;}export {wordBreak}