44 回溯算法解单次拆分II

2023-12-20 17:49:59

问题描述:给定一个非空字符串s和一个包含非空单次的词典wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单次都在词典中,返回这些所有可能的句子。

回溯算法求解:dfs算法中用一个index记录当前所在非空字符串的位置,并遍历位置后的所有元素,倘若当前元素与后续元素出现在wordDict中,则加入临时链表中,更新index进入下一个dfs中,当这个函数退出时,去除这个元素,并进入新一次的循环判断中;

public void dfs(String s,int index,List<String>wordDict,List<List<String>>res,ArrayList<String>templist)
{

if(index==s.length())
{
res.add(new List<String>(templist));
return;
}
for(int i=index;i<s.length();i++)
{
if(wordDict.contains(s.substring(index,i+1)))
{
templist.add(s.substring(index,i+1));
dfs(s,i+1,wordDict,res,templist);
templist.remove(templist.size()-1);
}else
{
continue;
}
}
}
public List<List<String>> dfs(String s,List<String>wordDict)
{
List<List<String>>list=new LinkedList<LinkedList<String>>res;
dfs(s,0,wordDict,res,new ArrayList<String>());
???????return list;
}

文章来源:https://blog.csdn.net/qq_52299902/article/details/135110026
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。