#299 Word Break

medium
javascript
blind75
dynamic-programming
string

Given a string s and a dictionary of strings wordDict, determine if s can be segmented into a space-separated sequence of dictionary words.

Rules:

  • Dictionary words can be reused unlimited times
  • All dictionary words are unique
  • Not all dictionary words must be used

Constraints:

  • 1 ≤ s.length ≤ 200
  • 1 ≤ wordDict.length ≤ 100
  • 1 ≤ wordDict[i].length ≤ 20
  • All strings contain only lowercase English letters

Examples:

// Example 1:
console.log(wordBreak("neetcode", ["neet", "code"]));
// Output: true
// Explanation: "neetcode" = "neet" + "code"

// Example 2:
console.log(wordBreak("applepenapple", ["apple", "pen"]));
// Output: true
// Explanation: "applepenapple" = "apple" + "pen" + "apple"

// Example 3:
console.log(wordBreak("catsincars", ["cats", "cat", "sin", "in", "car"]));
// Output: false
// Explanation: Cannot be segmented with given words