首页 > 试题广场 >

possible sentences

[编程题]possible sentences

热度指数：919 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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.

输入描述:

s ="catsanddog"
dict ="cat", "cats", "and", "sand", "dog"

输出描述:

[cats and dog, cat sand dog]

示例1

输入

s ="catsanddog"
dict ="cat","cats","and","sand","dog"

输出

[cats and dog, cat sand dog]

算法知识视频讲解

牛客题解官

发表于 2020-06-05 18:37:14

题解：考察点：深度优先搜索，字典树，剪枝易错点：本题的输入不是直接可用的，需要对输入进行字符串解析，同时由于输入带有空格，如果直接用会无法读入，建议使用按行进行读入。对于输入的解析，建议使用标记法，设置一个变量，当处于有效区域时，把标记为，当处于无效区域时，把标记为。这样保证有效部分能够很好展开全文