Word Break

The key idea

Let dp[i] mean the prefix s[0:i] can be fully segmented into dictionary words. dp[0] is true (the empty prefix). For each end i, scan every split point j < i: if dp[j] is true and the chunk s[j:i] is in the dictionary, then dp[i] is reachable too. The answer is dp[n].

Problem

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 wordDict may be reused multiple times in the segmentation.

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

Examples

Input: s = "leetcode", wordDict = ["leet","code"] Output: true

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false

Complexity

Time: O(n^2) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →