1-D Dynamic Programming Take it or skip it
519. Word Break
You are given a string s and a list of words, wordDict. Return true if s can be cut into pieces so
that every piece is a word from the list. Otherwise return false.
Every letter of s belongs to exactly one piece, and the pieces keep their order. A word can be used any
number of times, and some words may not be used at all.
Example 1
Input: s = "icecreamcone"
wordDict = ["ice",
"cream",
"icecream",
"cone",
"con"]
trueExplanation: ice cream cone works, and so does icecream cone. One way is enough.
Example 2
Input: s = "bedroomlamp"
wordDict = ["bed",
"room",
"bedroom",
"lam",
"lamps"]
falseExplanation: Both bed room and bedroom reach lamp, and lamp cannot be cut. lam leaves a lone p, and
lamps is longer than what is left.
Example 3
Input: s = "hahaha", wordDict = ["ha"]
trueExplanation: A word can be used again and again: ha ha ha.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ s.length ≤ 1051 ≤ wordDict.length ≤ 1041 ≤ wordDict[i].length ≤ 20sand every word hold only lowercase English letters- The words in
wordDictare all different.
Clarifying questions
What you would ask an interviewer before writing any code.