Word Break
MediumDynamic Programming
Given a string s and a list of words word_dict, return True if s can be cut into one or more pieces such that every piece is a word in word_dict, and False otherwise.
- The pieces must appear in order and together cover all of
s: no characters may be skipped or left over. - A dictionary word may be used any number of times, and not every word has to be used.
Example 1
- Input:
- s = "sunflowerpot", word_dict = ["flower", "sun", "pot", "flow", "sunflow"]
- Output:
- True
- Explanation
sun+flower+potworks. Grabbing the longer prefixsunflowfirst would be a dead end, becauseerpotcannot be split, so a correct solution has to consider more than one cut.
Example 2
- Input:
- s = "applepie", word_dict = ["apple", "ap", "plepi", "pi"]
- Output:
- False
- Explanation
- The last piece must end in
e, and the only word ending ineisapple, butapplepiedoes not end withapple. So no split exists.
Example 3
- Input:
- s = "abab", word_dict = ["ab"]
- Output:
- True
- Explanation
abis used twice:ab+ab.
Constraints
1 <= s.length <= 3001 <= word_dict.length <= 10001 <= word_dict[i].length <= 20sand every word contain only lowercase English letters- All words in
word_dictare distinct