Word Break
Understand how to apply dynamic programming to determine if a string can be segmented into a sequence of dictionary words. This lesson helps you break down the problem logically and implement an efficient solution, preparing you for similar coding interview challenges.
We'll cover the following...
Statement
Given a string, s, and a dictionary of strings, word_dict, 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 -
word_dict.length -
word_dict[i].length -
sandword_dict[i]consist of only lowercase English letters. -
All the strings of
word_dictare 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.
def word_break(s, word_dict):# Replace this placeholder return statement with your codereturn False