Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
分析如下：
题目意思是，给定词典的情况下，看看原字符串能不能全部成功地被给定的词典分割。也就是说，无论对原字符串怎么切割，只要切割后的那些字符串都在dict中即可。比如："leetcode"可以切割成"le","et","code"，只要dict包含这三个字符串就行。例子中当对字符串切割成"leet","code"时，刚好这两个字符串都在dict中，返回true。
一开始，最自然的想法是，使用递归。如果s本身就在dict中，返回true，否则就从前往后遍历字符串，取前面子串，当前面部分在dict中，就递归判断剩下的字符串。
见代码：但是递归会超时
class Solution { public boolean wordBreak(String s, List<String> wordDict) { return helper(s,wordDict,0); } public boolean helper(String s,List<String> word,int index){ if(word.contains(s.substring(index))) return true; for(int i=index;i<s.length()-1;i++){ if(word.contains(s.substring(index,i+1))&&helper(s,word,i+1)){ return true; } } return false; } }
使用动态规划，用一个数组存放从开头第一个字符到第i个字符(前面长度为i的字符串)能否切分成功flag[i]。i从1开始。
判断第i个字符这里的flag[i]，只要找到第i个字符前面的位置j上，flag[j]为true，而且从第j+1个字符到i个字符的字符串在dict中，则表示从第一个元素到第i个元素的字符串符合要求，flag[i]=true；
比如计算leetcode的分割方式，假设计算从开头长度为5的字符串(leetc)是否符合要求，也就是求flag[5]。只要前面有一个满足：flag[j]=true(j<5),而且从第j+1个元素到第5各元素的字符串在dict中，就行。
class Solution { public boolean wordBreak(String s, List<String> wordDict) { /* 使用动态规划，用一个数组存放从开头第一个字符到第i个字符(前面长度为i的字符串)能否切分成功flag[i]。i从1开始。 判断第i个字符这里的flag[i]，只要找到第i个字符前面的位置j上，flag[j]为true，而且从第j+1个字符到i个字符的字符串在dict中，则表示从第一个元素到第i个元素的字符串符合要求，flag[i]=true； */ if(wordDict.contains(s)) return true; //数组表示从开头到第i个元素(前面长度为i的字符串)能否切分成功flag[i]。i从1开始 boolean[] flag=new boolean[s.length()+1]; flag[0]=true; //0用于判断第一个元素 for(int i=1;i<=s.length();i++){ //这里i表示字符串的第i个元素，这里没有从0开始 /*判断第i个元素前面各个长度的字符串的情况，当长度j的字符串（从第一个元素开始到第j个元素）能够切分，那么就判断从第j+1个元素到第i个元素这个字符串在不在dict中。注意使用substring时下标是从0开始，要注意 */ for(int j=0;j<i;j++){ if(flag[j]&&wordDict.contains(s.substring(j,i))) { flag[i]=true;//i=0时，是字符串的第一个字符，所以在falg中下标为1。 break; } } } return flag[s.length()]; } }