Word Break

medium

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.

Test Cases

Copy an input into the main harness and Run to verify

Input

s = "leetcode", wordDict = ["leet","code"]

Expected Output

true

Explanation: Return true because "leetcode" can be segmented as "leet code".

Input

s = "applepenapple", wordDict = ["apple","pen"]

Expected Output

true

Explanation: Note that you are allowed to reuse a dictionary word.

Input

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Expected Output

false

Constraints

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
All the strings of wordDict are unique.

Hints

Hint 1 — click to reveal

Let dp[i] mean 'the first i characters can be segmented'.

Hint 2 — click to reveal

dp[i] is true when some j < i has dp[j] true and s[j..i) in the dictionary.

Java Compiler