当前仅显示指定条件回帖 [ 展开查看全部 ]
文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / word-break-ii
文件大小:
729.00 B
下载地址:
文本预览:
## [Word Break](../word-break) with traceback
In order to output all solutions,
just change P from `boolean` to a collection which contains all parent index.
```
0 1 2 3 4 5 6 7 8 9 A
* c a t s a n d d o g
0 0 3 7
4
P[3] = [0]
P[4] = [0]
P[7] = [3, 4]
P[10] = [7]
```
## Recover strings using DFS
To find all strings break at breakpoint, just using DFS to find out them.
* 10, 7, 3, 0: dog sand cat
* 10, 7, 4, 0: dog and cats
### Note:
offsets here is 1 larger than the original offset.
So, `7..10` here is to start form the next element, the 8th to the 11th(exclusive).
Luckily, restore the `S[8th..11th]` is just the same as `S[7..10]`,
Because index of S starts from `0`.
In order to output all solutions,
just change P from `boolean` to a collection which contains all parent index.
```
0 1 2 3 4 5 6 7 8 9 A
* c a t s a n d d o g
0 0 3 7
4
P[3] = [0]
P[4] = [0]
P[7] = [3, 4]
P[10] = [7]
```
## Recover strings using DFS
To find all strings break at breakpoint, just using DFS to find out them.
* 10, 7, 3, 0: dog sand cat
* 10, 7, 4, 0: dog and cats
### Note:
offsets here is 1 larger than the original offset.
So, `7..10` here is to start form the next element, the 8th to the 11th(exclusive).
Luckily, restore the `S[8th..11th]` is just the same as `S[7..10]`,
Because index of S starts from `0`.
点赞
回复
X