首页 > 试题广场 >

单词拆分(二)

[编程题]单词拆分(二)
  • 热度指数：1581 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串 s 和一个字符串数组 dic ，在字符串 s 的任意位置添加任意多个空格后得到的字符串集合是给定字符串数组 dic 的子集（即拆分后的字符串集合中的所有字符串都在 dic 数组中），你可以以任意顺序 返回所有这些可能的拆分方案。

数据范围：字符串长度满足 ，数组长度满足 ，数组中字符串长度满足
示例1

输入

"nowcoder",["now","coder","no","wcoder"]

输出

["no wcoder","now coder"]
示例2

输入

"nowcoder",["now","wcoder"]

输出

[]
示例3

输入

"nowcoder",["nowcoder"]

输出

["nowcoder"]
示例4

输入

"nownowcoder",["now","coder"]

输出

["now now coder"]

说明

你可以重复使用 dic 数组中的字符串
算法知识视频讲解
开通博客
头像 牛客313925129号
发表于 2022-03-02 16:30:49
题意理解 把一个字符串s拆分为若干个子串，要求每个子串都是数组dic中的某个元素。拆分的方***有多种，要求输出所有的方法，每一种拆分方法用空格将子串隔开从而形成一个字符串。 方法一 深度优先搜索 看到题目要求的数据较小，考虑使用深度优先搜索枚举所有的可能性。如果s可以被正确拆分，说明其头部的一段子 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 AimerAimer
发表于 2022-02-03 17:45:51
题意：         给定一个字符串和一个字符串数组，在字符串的任意位置添加空格后得到的字符串集合是给定字符串数组的子集，请输出可能的拆分方案。    &nbs 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 CroMarmot
发表于 2022-02-22 10:14:04
单词拆分(二) 题意 给定一个字典，和一个字符串，把字符串拆分成字典的子集 方法 递归搜索 分析 因为要拆分成字典的子集 所以，字符串的开头一定匹配某个单词 如果我们枚举找到一个单词，也就从这个单词的结尾知道了下一个拆分的位置 对于下一个拆分的位置，操作和初始单词的操作相同，都是从头部开始匹配 所以 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 超级大米
发表于 2021-12-07 20:19:24
用到了动态规划和字典查询，f(n)表示从从0到第n个字符有哪些解，则f(n) = (字母(0到n)如果在字典中，则并入f(0)的解) + (字母(1到n)如果在字典中，则并入f(1)的解).... (字母(n-1到n)如果在字典中，则并入f(n-1)的解),最终输出f(n) class Soluti 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客964891830号
发表于 2021-11-10 23:24:23
采用动态规划算法 "> // write code here vector<vector<string>> dp(s.length()+1, vector<string>()); set<string> wordDict; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 刷刷题能通过考试
发表于 2024-01-14 14:20:43
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @param dic string字符串一维数组 # @return string字符串一维数组 # class Solution: # 返回该字符串 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-08-05 14:08:19
import java.util.*; /** * NC182 单词拆分(二) * @author d3y1 */ public class Solution { private int len; private ArrayList<String> list = 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2022-02-23 23:12:07
单词拆分(二) 题目描述 给定一个字符串 s 和一个字符串数组 dic ，在字符串 s 的任意位置添加任意多个空格后得到的字符串集合是给定字符串数组 dic 的子集（即拆分后的字符串集合中的所有字符串都在 dic 数组中），你可以以任意顺序 返回所有这些可能的拆分方案。 方法一：递归的方法 解题思路 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 17c89
发表于 2024-06-08 17:37:00
import java.util.*; /** * NC182 单词拆分(二) * @author d3y1 */ public class Solution { private int len; private ArrayList<String> list = 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 记忆化搜索 字符串 哈希 字典树
难度：
8条回答 5292浏览

热门推荐

通过挑战的用户

查看代码

相关试题

单词拆分(二)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号