582. Word Break II

Description

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

Example

Example 1:

Input："lintcode"，["de","ding","co","code","lint"]

Output：["lint code", "lint co de"]

Explanation：

insert a space is "lint code"，insert two spaces is "lint co de".

Example 2:

Input："a"，[]

Output：[]

Explanation：dict is null.

思路：

优化方案1

用 Word Break 这个题的思路，使用 is_possible[i] 代表从 i 开始的后缀是否能够被 break，在 DFS 找所有方案的时候，通过 is_possible 可以进行可行性剪枝.

优化方案2

直接使用 memo[i] 记录从位置 i 开始的后缀，能够被 break 出来的所有方案

代码：

优化方案一：

自己写的，可能有点笨。

优化方案2