#140
Word Break II
expert · 1295 · lc hard +32 · verified · 55.2% accepted · 7,540 likes · top 48%
Description
Given a string s and a dictionary wordDict, insert spaces into s to form sentences where every word exists in wordDict. Return all such sentences in any order.
Dictionary words may be reused multiple times within the same sentence.
Example 1:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
Example 2:
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
Code
1
2
3