LeetCode-139-wordsplitting

wordsplitting题目描述：给定一个非空字符串s和一个包含非空词的列表wordDict，判断s是否可以被空格分割成字典中出现的一个或多个单词。解释：字典中的单词在拆分时可以重复使用。您可以假设字典中没有重复的单词。例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。解法一：穷举法采用穷举+递归的方法求解，效率低。具体处理过程如下：如果当前字符串为null或者为空，可以默认通过字符串字典进行分割，直接返回true；否则，遍历字符串字典中的字符串：如果恰好有一个字符串与当前字符串相等且长度相同，则直接返回true；如果一个字符串与当前字符串相等但长度不一致，则递归判断后面的字符String，并返回判断结果。最后返回最终判断的结果。方案二：动态规划首先将字符串字典初始化到哈希表wordDictSet中，用于快速查找；然后初始化一个长度为原字符串长度加1的dp数组，并将数组的第一个元素初始化为true；然后遍历字符串，判断从0到i的字符串是否可以被字符串字典拆分：判断逻辑是0到j的字符串可以被字符串字典拆分（这个是根据前面的计算得到的），而j到i的字符串在字符串字典中。最后返回dp数组的最后一个元素作为最终结果。importjava.util.ArrayList;importjava.util.HashSet;importjava.util.List;importjava.util.Set;publicclassLeetCode_139{privatestaticbooleanflag=false;/***详尽方法**@params*@paramwordDict*@return*/publicstaticbooleanwordBreak(Strings,ListwordDict){if(s==null||s.length()==0){返回真；}for(Stringword:wordDict){if(flag){返回标志；}if(s.startsWith(word)){if(s.length()==word.length()){//如果当前字符在字符串字典中如果某个字符串匹配且长度相同，则它表示当前字符串可以被字符串字典拆分，returntruereturntrue；}//如果当前字符串被字符串字典中的字符串分割，也是如果还有字符需要判断，递归判断后面的字符串flag=wordBreak(s.substring(word.length()),wordDict);}}返回标志；}/***动态规划**@params*@paramwordDict*@return*/publicstaticbooleanwordBreak2(Strings,ListwordDict){//将字符串字典初始化到哈希表中以便快速查找SetwordDictSet=newHashSet<>(wordDict);布尔[]dp=新布尔[s.length()+1];//默认空字符串可以从字符串字典中分出，初始设置为truedp[0]=true;//判断从0到i的字符是否可以划分到字符串字典中for(inti=1;i<=s.length();i++){for(intj=0;jwordDict=newArrayList<>();wordDict.add("苹果");wordDict.add("笔");System.out.println(wordBreak(s,word听写));System.out.println(wordBreak2(s,wordDict));}}[每日寄语]相信机会总会有的，不要跟自己较劲，顺势而为，像太极推手一样，顺势而为，要学会利用周围的资源