s*******m 发帖数: 228 | 1 leetcode原题word breakII,输出一种分割即可
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"].
我考虑的做法是,先动态规划找到可分割的点dp[n+1],然后倒着遍历s,查找单词。
follow up: 英语中,几个字母组成单词的概率远小于不是单词的概率,怎么优化?
follow问题,该怎么优化???????????? | e*******7 发帖数: 347 | | b*****n 发帖数: 618 | | s*******m 发帖数: 228 | 4 请详细讲讲啊
【在 b*****n 的大作中提到】 : 建个trie
| b*********n 发帖数: 26 | 5 In your DP, you are caching the exist words,
you can cache the non exist words |
|