首页 > 代码库 > (待解决)leecode 分词利用词典分词 word break
(待解决)leecode 分词利用词典分词 word break
不戚戚于贫贱，不汲汲于富贵 ---五柳先生
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".
搜索--》自顶向下的动态规划（备忘录法）》自底向下动态规划
这些思想一直在使用中
1.递归（搜索）
学习递归时候，老师说他的好处 是简单，其实递归的思路是暴力搜索的方法，所以写的人需要考虑的问题很少，但是栈的调用很耗时，同时可能会出现栈溢出。但是他只做自己需要干的事情，，同时他需要干的事情他会重复做。这为后面的自顶向下的优化做了铺垫。
public class Solution { public boolean wordBreak(String s, Set<String> dict) { if(s=="") return true; for(int i=0;i<s.length();i++) { String s1=s.substring(0,i+1); //枚举所有以0为开头的的字符串 if(dict.contains(s1)&&wordBreak(s.substring(i+1),dict)) { return true; } } return false; }}结果是：
Last executed input:"acaaaaabbbdbcccdcdaadcdccacbcccabbbbcdaaaaaadb", ["abbcbda","cbdaaa","b","dadaaad","dccbbbc","dccadd","ccbdbc","bbca","bacbcdd","a","bacb","cbc","adc","c","cbdbcad","cdbab","db","abbcdbd","bcb","bbdab","aa","bcadb","bacbcb","ca","dbdabdb","ccd","acbb","bdc","acbccd","d","cccdcda","dcbd","cbccacd","ac","cca","aaddc","dccac","ccdc","bbbbcda","ba","adbcadb","dca","abd","bdbb","ddadbad","badb","ab","aaaaa","acba","abbb"]
2.超时了，如何优化呢，博主在一本书上看过，是自顶向下动态规划，同学们可以查查，其实就是记住了他重复做的事情。
dp[i][j]表示两者之间是否在词典中。
dp[i][j]=dp[i][k] && dp[k+1][j] (i+1=<k<j-1)
public class Solution { // int dp(int i,int j,String s,Set<String> dict,int d[][]) // get the i to j is exit in the dict { if(d[i][j]==1) return 1; if(d[i][j]==-1) return -1; if(dict.contains(s.substring(i,j+1))) { d[i][j]=1; return 1; } else { for(int k=i;k<j;k++) { if(dp(i,k,s,dict,d)==1&&dp(k+1,j,s,dict,d)==1) { d[i][j]=1; return 1; } } return -1; } } public boolean wordBreak(String s, Set<String> dict) { int len=s.length(); int d[][]=new int[len][len]; int ans=dp(0,len-1,s,dict,d); if(ans==1) return true; return false; }}
错了，还是超时，
3.最后的自定向下方法了，填表，那些专业人士都叫打表。