Word Break
Medium
Array
Hash Table
String
Dynamic Programming
Trie
Given a string `s` and a dictionary of strings `wordDict`, return `true` *if* `s` *can be segmented into a space-separated sequence of one or more dictionary words*. **Note** that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Example 2
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Example 3
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Constraints

  • •1 <= s.length <= 300
  • •1 <= wordDict.length <= 1000
  • •1 <= wordDict[i].length <= 20
  • •s and wordDict[i] consist of only lowercase English letters.
  • •All the strings of wordDict are unique.
Time Complexity
O(n²)
Space Complexity
O(n)
14
Case 1
Input: "leetcode" ["leet","code"]
Expected: true
Case 2
Input: "applepenapple" ["apple","pen"]
Expected: true
Case 3
Input: "catsandog" ["cats","dog","sand","and","cat"]
Expected: false