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.
For example,
given*s* = "catsanddog",
*dict* = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
第一步建立字符串中分词的状态，设 f[i] 为 boolean 状态表示以 s[0,i]能被
dict 分割，状态方程：
f�[i�][j] = true if s[i][j] ∈ ���dict
| c | a | t | s | a | n | d | d | o | g | |
|---|---|---|---|---|---|---|---|---|---|---|
| c | F | F | T | T | F | F | F | F | F | F |
| a | F | F | F | F | F | F | F | F | F | |
| t | F | F | F | F | F | F | F | F | ||
| s | F | F | F | T | F | F | F | |||
| a | F | F | T | F | F | F | ||||
| n | F | F | F | F | F | |||||
| d | F | F | F | F | ||||||
| d | F | F | T | |||||||
| o | F | F | ||||||||
| g | F |
第二部通过 DFS 恢复成句子。
网友评论