给定一个字符串 s 和一个字符串数组 dic ，在字符串 s 的任意位置添加任意多个空格后得到的字符串集合是给定字符串数组 dic 的子集（即拆分后的字符串集合中的所有字符串都在 dic 数组中），你可以以任意顺序 返回所有这些可能的拆分方案。
数据范围：字符串长度满足 
，数组长度满足 
，数组中字符串长度满足
[编程题]单词拆分(二)
- 热度指数：1637 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例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 数组中的字符串
dfs 解法
1. 以 s 为切入点，从第一个字符开始遍历，找到匹配的上的部分，然后继续寻找，直到找到尾部，返回已经匹配上的字符串数组即可
注意：
① 这道题只有完全匹配上和匹配不上两种可能，因此可以直接从第0个位置的字符开始匹配，属于是简化了解题过程，如果说要求部分匹配也要返回，那就不能这么做了，那就必须考虑从 s 的任意位置开始匹配的所有情况了。
② 回溯的时候切勿使用 currentList.remove(word) 方法, 因为如果 list 中包含多个重复元素，该操作无法移除最后一个元素，所以必须使用 currentList.remove(currentList.size() - 1)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串一维数组
* @return string字符串一维数组
*/
public String[] wordDiv(String s, String[] dic) {
List<String> result = new ArrayList<>();
Set<String> wordDict = new HashSet<>(Arrays.asList(dic));
backtrack(s, wordDict, 0, new ArrayList<String>(), result);
String[] res = new String[result.size()];
for(int i=0; i<result.size(); i++)
res[i] = result.get(i);
return res;
}
private void backtrack(String s, Set<String> wordDict, int start,
List<String> currentList, List<String> result) {
if (start == s.length()) {
result.add(String.join(" ", currentList));
return;
}
for (int end = start + 1; end <= s.length(); end++) {
String word = s.substring(start, end);
if (wordDict.contains(word)) {
currentList.add(word);
backtrack(s, wordDict, end, currentList, result);
currentList.remove(currentList.size() - 1);
}
}
}
}
发表于 2024-07-16 17:36:52
回复(0)
import java.util.*;
/**
* NC182 单词拆分(二)
* @author d3y1
*/
public class Solution {
private int len;
private ArrayList<String> list = new ArrayList<>();
private HashSet<String> set = new HashSet<>();
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param dic string字符串一维数组
* @return string字符串一维数组
*/
public String[] wordDiv (String s, String[] dic) {
// return solution1(s, dic);
// return solution2(s, dic);
return solution3(s, dic);
// return solution4(s, dic);
}
/**
* 动态规划
*
* dp[i]表示字符串s前i个字符组成的字符串能否拆分
*
* dp[i] = dp[j] && check(s[j..i−1]) , 0<=j<i
* check(s[j..i−1]) => map.getOrDefault(suffix, false)
* 其中 check(s[j..i−1]) 表示子串s[j..i−1]是否出现在字典中
*
* @param s
* @param dic
* @return
*/
private String[] solution1(String s, String[] dic){
int n = s.length();
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int len;
HashMap<String, Boolean> map = new HashMap<>();
for(String word: dic){
len = word.length();
min = Math.min(min, len);
max = Math.max(max, len);
map.put(word, true);
}
boolean[] dp = new boolean[n+1];
dp[0] = true;
ArrayList<String>[] list = new ArrayList[n+1];
for(int i=1; i<=n; i++){
int gap;
String suffix;
for(int j=i-1; j>=0; j--){
gap = i-j;
if(gap < min){
continue;
}
if(max < gap){
break;
}
suffix = s.substring(j, i);
if(dp[j] && map.getOrDefault(suffix, false)){
dp[i] = true;
if(list[i] == null){
list[i] = new ArrayList<String>();
}
if(list[j]!=null && list[j].size() > 0){
for(String part: list[j]){
list[i].add(part + " " + suffix);
}
}else{
list[i].add(suffix);
}
}
}
}
int size = 0;
if(list[n] != null){
size = list[n].size();
}
String[] result = new String[size];
for(int i=0; i<size; i++){
result[i] = list[n].get(i);
}
return result;
}
/**
* 动态规划: 简化
*
* dp[i]表示字符串s前i个字符组成的字符串的所有拆分方案
*
* 判断是否可拆分
* dp[j]!=null && map.getOrDefault(suffix, false) , 0<=j<i
* check(s[j..i−1]) => map.getOrDefault(suffix, false)
* 其中 check(s[j..i−1]) 表示子串s[j..i−1]是否出现在字典中
*
* @param s
* @param dic
* @return
*/
private String[] solution2(String s, String[] dic){
int n = s.length();
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int len;
HashMap<String, Boolean> map = new HashMap<>();
for(String word: dic){
len = word.length();
min = Math.min(min, len);
max = Math.max(max, len);
map.put(word, true);
}
ArrayList<String>[] dp = new ArrayList[n+1];
dp[0] = new ArrayList<>();
for(int i=1; i<=n; i++){
int gap;
String suffix;
for(int j=i-1; j>=0; j--){
gap = i-j;
if(gap < min){
continue;
}
if(max < gap){
break;
}
suffix = s.substring(j, i);
if(dp[j]!=null && map.getOrDefault(suffix, false)){
if(dp[i] == null){
dp[i] = new ArrayList<>();
}
if(dp[j]!=null && dp[j].size() > 0){
for(String part: dp[j]){
dp[i].add(part + " " + suffix);
}
}else{
dp[i].add(suffix);
}
}
}
}
int size = 0;
if(dp[n] != null){
size = dp[n].size();
}
String[] result = new String[size];
for(int i=0; i<size; i++){
result[i] = dp[n].get(i);
}
return result;
}
/**
* dfs: 字典树Trie
* @param s
* @param dic
* @return
*/
private String[] solution3(String s, String[] dic){
Trie root = new Trie();
for(String word: dic){
root.insert(word);
}
len = s.length();
for(int i=1; i<=len; i++){
dfs(s, root, 0, i, "");
}
String[] result = new String[list.size()];
for(int i=0; i<list.size(); i++){
result[i] = list.get(i);
}
return result;
}
/**
* 递归
* @param s
* @param root
* @param i
* @param j
* @param result
*/
private void dfs(String s, Trie root, int i, int j, String result){
String sub = s.substring(i, j);
if(root.search(sub)){
if(j == len){
list.add(result+sub);
}else{
String pre = s.substring(j, j+1);
if(root.prefixNumber(pre) > 0){
for(int k=j+1; k<=len; k++){
dfs(s, root, j, k, result+sub+" ");
}
}
}
}
}
/**
* 字典树Trie
*/
private class Trie {
private Trie[] children;
boolean isEnd;
private int count;
public Trie(){
children = new Trie[75];
isEnd = false;
count = 0;
}
public void insert(String word){
Trie curr = this;
int index;
for(char ch: word.toCharArray()){
index = ch - '0';
if(curr.children[index] == null){
curr.children[index] = new Trie();
}
curr = curr.children[index];
curr.count++;
}
curr.isEnd = true;
}
public void delete(String word){
Trie curr = this;
int index;
for(char ch: word.toCharArray()){
index = ch - '0';
if(curr.children[index] != null){
curr = curr.children[index];
curr.count--;
}
}
if(curr.count == 0){
curr.isEnd = false;
}
}
public boolean search(String word){
Trie curr = this;
int index;
for(char ch: word.toCharArray()){
index = ch - '0';
if(curr.children[index] == null){
return false;
}
curr = curr.children[index];
}
if(!curr.isEnd){
return false;
}
return true;
}
public int prefixNumber(String pre){
Trie curr = this;
int index;
for(char ch: pre.toCharArray()){
index = ch - '0';
if(curr.children[index] == null){
return 0;
}
curr = curr.children[index];
}
return curr.count;
}
}
/**
* dfs: HashSet
* @param s
* @param dic
* @return
*/
private String[] solution4(String s, String[] dic){
len = s.length();
for(String word: dic){
set.add(word);
}
dfs(s, 0, "");
String[] result = new String[list.size()];
for(int i=0; i<list.size(); i++){
result[i] = list.get(i).trim();
}
return result;
}
/**
* 递归
* @param s
* @param i
* @param result
*/
private void dfs(String s, int i, String result){
if(i == len){
list.add(result);
}
String sub = "";
// for(int j=i; j<len; j++){
// sub += s.charAt(j);
// if(set.contains(sub)){
// dfs(s, j+1, result+sub+" ");
// }
// }
for(int j=i+1; j<=len; j++){
sub = s.substring(i, j);
if(set.contains(sub)){
dfs(s, j, result+sub+" ");
}
}
}
}
发表于 2025-02-27 13:21:45
回复(0)
Java深搜
private void dfs(String s, int index, String[] dic, ArrayList<ArrayList<String>> arrayLists, ArrayList<String> list) {
if (index == s.length()) {
arrayLists.add(new ArrayList<>(list));
} else {
for (String s1 : dic) {
if (s.substring(index).startsWith(s1)) {
list.add(s1);
dfs(s, index + s1.length(), dic, arrayLists, list);
list.remove(list.size() - 1);
}
}
}
}
public String[] wordDiv(String s, String[] dic) {
ArrayList<ArrayList<String>> arrayLists = new ArrayList<>();
ArrayList<String> list = new ArrayList<>();
HashSet<String> set = new HashSet<>();
int index = 0;
dfs(s, 0, dic, arrayLists, list);
for (ArrayList<String> arrayList : arrayLists) {
StringBuilder sb = new StringBuilder();
arrayList.stream().forEach(str -> sb.append(str + " "));
sb.deleteCharAt(sb.length() - 1);
set.add(sb.toString());
}
String[] strings = new String[set.size()];
for (String s1 : set) {
strings[index++] = s1;
}
return strings;
}
发表于 2022-11-21 10:01:09
回复(0)
为什么java怎么提交都会报Main.java:28: error: incompatible types: ArrayList cannot be converted to String[]
发表于 2022-09-28 11:00:47
回复(1)
class Solution:
def wordDiv(self , s: str, dic: List[str]) -> List[str]:
# write code here
res = []
path = []
index = 0
def backtrack(index):
if index >= len(s):
res.append(' '.join(path[:]))
return
for i in range(index, len(s)):
p = s[index : i + 1]
if p in dic:
path.append(p)
else:
continue
backtrack(i + 1)
path.pop()
backtrack(index)
return res
发表于 2022-08-15 05:35:01
回复(0)
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @param dic string字符串一维数组 # @return string字符串一维数组 # class Solution: """ 题目： NC182 单词拆分(二) https://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5?tpId=117&&tqId=39349&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking https://leetcode-cn.com/problems/word-break-ii/ 算法： 记忆化搜索 回溯 对于字符串s，如果某个前缀是单词表中的单词，然后对s剩余部分继续拆分。如果可以将整个字符串s拆分成单词列表中的单词，则可以得到1个句子。在对s的剩余部分拆分得到1个句子之后，将拆分出的第1个单词（即s的前缀）添加到句子的头部，即可得到1个完成的句子。上述过程可以通过回溯实现。 使用哈希表存储字符串s的每个下标和该下标开始的部分可以组成的句子列表，在回溯过程中，如果遇到已经访问过的下标，则可以直接从哈希表得到结果，而不需要重复计算。如果到某个下标发现无法匹配，则哈希表中该下标对应的是空列表，因此可以对不能拆分的情况进行剪枝。 复杂度： 时间复杂度：O(n * 2^n) 空间复杂度：O(n * 2^n) """ def wordDiv(self, s, dic): # write code here def dfs(i): if i == n: return [[]] ans = [] for j in range(i + 1, n + 1): word = s[i:j] if word in wordSet: nextWordDivs = dfs(j) for nextWordDiv in nextWordDivs: ans.append(nextWordDiv[:] + [word]) return ans n = len(s) wordSet = set(dic) divList = dfs(0) return [' '.join(words[::-1]) for words in divList] if __name__ == '__main__': s = Solution() str, dic = "nowcoder", ["now", "coder", "no", "wcoder"] # str, dic = "nowcoder", ["now", "wcoder"] # str, dic = "nowcoder", ["nowcoder"] # str, dic = "aaaaaaaaaaaaaaaaaaaa", ["a", "aa", "aaa", "aaaa", "aaaaa", # "aaaaaa", "aaaaaaa", "aaaaaaaa", # "aaaaaaaaa", "aaaaaaaaaa"] res = s.wordDiv(str, dic) print res
发表于 2022-07-07 10:12:05
回复(0)
static Set<String> list=new HashSet<>();
public String[] wordDiv (String s, String[] dic) {
StringBuilder st=new StringBuilder();
findWord(st,s,dic);
String[] sa=new String[list.size()];
list.toArray(sa);
return sa;
}
void findWord(StringBuilder ss, String sc, String[] dic){
if(sc.length()==0){
ss.delete(ss.length()-1,ss.length());
list.add(ss.toString());
ss.append(" ");
return;
}
for(int i=0;i<dic.length;i++){
if(dic[i].length()<=sc.length()&&sc.substring(0,dic[i].length()).equals(dic[i]))
{
ss.append(dic[i]+" ");
findWord(ss,sc.substring(dic[i].length()),dic);
ss.delete(ss.length()-dic[i].length()-1,ss.length());
}
}
}
发表于 2022-05-31 19:28:21
回复(0)
深度优先搜索，简洁易懂
HashSet<String> set;
List<String> ret;
public String[] wordDiv(String s, String[] dic) {
set = new HashSet<>();
for (String s1 : dic) {
set.add(s1);
}
ret = new ArrayList<>();
for (int i = 0; i <= s.length(); i++) {
if (set.contains(s.substring(0, i))) {
dfs(s, i, s.substring(0, i));
}
}
return ret.toArray(new String[0]);
}
private void dfs(String s, int index, String ans) {
// 递归出口
if (s.length() == index) {
ret.add(ans);
return;
}
for (int i = index; i <= s.length(); i++) {
if (set.contains(s.substring(index, i))) {
dfs(s, i, ans + " " + s.substring(index, i));
}
}
}
编辑于 2022-02-12 20:00:15
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
