给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
思路
- 动态规划
- 状态的定义为：以 s[i] 结尾的子字符串是否可以被空格拆分为一个或多个在字典中出现的单词。
代码
public class Solution {
public List<String> wordBreak(String s,List<String> wordDict) {
int len = s.length();
// dp[] 数组，dp[i] 表示以 s[i] 结尾的子字符串是否可以被空格拆分为一个或多个在字典中出现的单词。
boolean[] dp = new boolean[len];
// 预处理，将列表变成Set
Set<String> wordSet = new HashSet<>();
for (String word : wordDict) {
wordSet.add(word);
}
// dp初始状态
for (int r = 0; r < len; r++) {
// 初始化
if (wordSet.contains(s.substring(0,r+1))) {
dp[r] = true;
continue;// 包含字串，直接下一轮循环
}
for (int l = 0;l < r;l++) {
if (dp[l] && wordSet.contains(s.substring(l+1,r+1))) {
dp[r] = true;
break;// 拆分方案已找到
}
}
}
List<String> res = new ArrayList<>();
if (dp[len - 1]) {// 不可以直接拆分
LinkedList<String> queue = new LinkedList<>();
dfs(s,len-1,wordSet,res,queue,dp);
return res;
}
return res;
}
private void dfs(String s,int end, Set<String> wordSet,List<String> res,LinkedList<String> queue,boolean[] dp) {
// 剩余部分直接是一个单词，找到一个解
if (wordSet.contains(s.substring(0,end + 1))) {
queue.addFirst(s.substring(0, end + 1));
StringBuilder sb = new StringBuilder();
for (String word:queue) {
sb.append(word).append(" ");
}
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
queue.removeFirst();// 回溯
}
for (int i = 0;i < end; i++) {
if (dp[i]) {// 根据标记的位置进行字符串分割
String suffix = s.substring(i + 1, end + 1);
if (wordSet.contains(suffix)) {
queue.addFirst(suffix);
dfs(s,i,wordSet,res,queue,dp);
queue.removeFirst();// 回溯
}
}
}
}
}
//
class Solution {
public List<Integer> ele;
public List<String> seq;
public Map<String,Integer> map;
public int n=0;
public int maxp=0;
public String s;
public List<String> wordDict;
public int len;
public int[] dp;
public List<String> wordBreak(String s, List<String> wordDict) {
this.s=s;
this.wordDict=wordDict;
this.len=s.length();
dp=new int[len+1];
seq=new ArrayList<>();
ele=new ArrayList<>();
if(len==0) return seq;
map=new HashMap<>();
n=wordDict.size();
maxp=0;
for(int i=0;i<n;i++)
{
map.put(wordDict.get(i),i);
maxp=maxp<wordDict.get(i).length()?wordDict.get(i).length():maxp;
}
dp[0]=1;
dfs(len);
return seq;
}
public boolean dfs(int pos)
{
if(dp[pos]==-1)
return false;
if(dp[pos]==0)
dp[pos]=-1;
ele.add(pos);
if(pos==0)
{
StringBuilder sb=new StringBuilder();
for(int i=ele.size()-1;i>1;i--)
{
sb.append(s.substring(ele.get(i),ele.get(i-1)));
sb.append(" ");
}
sb.append(s.substring(ele.get(1),ele.get(0)));
seq.add(sb.toString());
}
for(int i=1;i<=maxp&&pos-i>=0;i++)
{
if(map.containsKey(s.substring(pos-i,pos)))
{
if (dfs(pos-i))
{dp[pos]=1;}
}
}
ele.remove(ele.size()-1);
return dp[pos]==1;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
