wordpress 新闻类网站,购物商城建设网站,繁体企业网站源码,内蒙古网站开发公司给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict#xff0c;在字符串中增加空格来构建一个句子#xff0c;使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明#xff1a;
分隔时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 …给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict在字符串中增加空格来构建一个句子使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明
分隔时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1
输入: s “catsanddog” wordDict [“cat”, “cats”, “and”, “sand”, “dog”] 输出: [ “cats and dog”, “cat sand dog” ]
代码
class Solution {ListString stringListnew ArrayList(); SetInteger checknew HashSet();int maxLen0,minLenInteger.MAX_VALUE;public ListString wordBreak(String s, ListString wordDict) {for(String word:wordDict)//获取单词的长度范围限制可选择的长度{maxLen Math.max(maxLen,word.length());minLen Math.min(minLen,word.length());}wBreak(s,0,wordDict,new ArrayList());return stringList;}public void wBreak(String s,int pos,ListString wordDict,ListString list) {if(poss.length())//边界{stringList.add( String.join( ,list));return;}if(check.contains(pos))return;int resLstringList.size();for(int iminLen;iposs.length()imaxLen;i){String subs.substring(pos,posi);for(String word:wordDict)//遍历单词{if(sub.equals(word)){list.add(word);wBreak(s,ipos,wordDict,list);list.remove(list.size()-1);//回溯}}}if(stringList.size()resL)//结果序列没有变说明该位置往后无法产生结果check.add(pos);}
}
