Word break
You get a string s of lowercase letters and a list words of dictionary words. Return True if you can cut s into pieces so that every piece is one of the words, and False otherwise.
- The pieces must cover all of
s, in order: no letter left over, and no letter in two pieces. - A word may be used any number of times, or not at all.
s = "sunflower", words = ["sun", "flow", "flower"]OutputTrueCut it as "sun" + "flower". The cut "sun" + "flow" would leave "er", which is not a word.
s = "redbluered", words = ["red", "blue"]OutputTrue"red" + "blue" + "red": the word "red" is used twice.
s = "bookend", words = ["book", "boo", "kend"]OutputTrue"boo" + "kend". Taking the longer "book" first leaves "end", which cannot be cut.
s = "seashells", words = ["sea", "seas", "hell", "shell"]OutputFalseBoth ways to cover "seashell" ("sea" + "shell" and "seas" + "hell") leave a lone "s" at the end.
1 ≤ len(s) ≤ 300
1 ≤ len(words) ≤ 1,000
1 ≤ len(word) ≤ 20 for every word
sand the words use only lowercase English letters, and the words are all different.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.