Word Break

Medium · 1-D Dynamic Programming

You are given a string and a list of allowed words. Determine whether the string can be split into a sequence of one or more of these words placed one after another with nothing left over. The same word from the list may be reused as many times as needed, and the split pieces must exactly cover the whole string with no extra or missing characters. Return true if such a split exists, otherwise false.

Examples

Input:  s = "leetcode", wordDict = ["leet", "code"]
Output: true
Why:    The string splits exactly into "leet" followed by "code", both of which are in the list.

Input:  s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Why:    It splits into "apple", "pen", "apple", reusing "apple" twice.

Input:  s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Why:    No combination of the given words can be concatenated to reproduce the string exactly; "og" is always left dangling.

Constraints

1 <= s.length <= 300, 1 <= wordDict.length <= 1000, 1 <= wordDict[i].length <= 20, s and wordDict[i] consist of lowercase English letters, all strings in wordDict are unique

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Word Break

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Word Break. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.