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 对 待判断字符串S 进行 DFS。查找每个字典的元素,如果匹配,S 跳到下一个坐标,直到S 全部检查完。
2 缺点: 考虑到S 是一个字符串,由很多a 组成,最后是b;字典就是a。这样会花很多时间。第一次对s的第一个a 检查,匹配;再第二个,第三个,直到最后一个不匹配;然后再重新对s的头两个 aa 对字典进行匹配...
3 时间是指数级别的
public boolean wordBreak(String s, Set<String> dict) { return worddfs(s,dict); } public boolean worddfs(String s,Set<String> dict){ if(s.equals("")){ return true; } for(int i=0;i<s.length();i++){ String temp = s.substring(0,i+1); if(dict.contains(temp)){ if(i==s.length()-1){ return true; } if(worddfs(s.substring(i+1),dict)){ return true; } } } return false; }
1 时间不行,有很多重复检查了。那么考虑从底向上的字典dfs。需要一个二维数组mp。
2 mp[i][j] 代表 S 从i 到j 是否可以匹配。只要存在k mp[i][k] 和 mp[k][j] 都为true的时候,mp[i][j] 也为true。
3 我们需要求的就是mp[0][n-1]
4 时间是O(n3)
public class Solution { public boolean wordBreak(String s, Set<String> dict) { if(s.length()==0){ return false; } int n = s.length(); boolean[][] ans = new boolean[n][n]; for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(dict.contains(s.substring(i,j+1))){ ans[i][j]=true; } } } for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ for(int k=i;k<=j;k++){ if(!ans[i][j]){ ans[i][j]=ans[i][k]&&ans[k+1][j]; } } } } return ans[0][n-1]; } }
1 虽然accept,但是时间不够好。继续思考。
2 发现其实我们要求的只是ans[0][n-1]。然后对于每个0行的元素,也就是string 0--i,只有在他之前的0-j是true和ans[j][i]是true的时候才true。
3 所以我们只要再多一个memo[n+1]的数组,来记录每个0-j是否为true,结合上面的ans数组,就可以判断了。
4 时间缩小到O(n2), dp的技巧让 空间换时间。
public class Solution { public boolean wordBreak(String s, Set<String> dict) { if(s.length()==0){ return false; } int n = s.length(); boolean[][] ans = new boolean[n][n]; for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ if(dict.contains(s.substring(i,j+1))){ ans[i][j]=true; } } } boolean[] memo = new boolean[n+1]; memo[0]=true; for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ if(memo[j]&&ans[j][i]){ memo[i+1]=true; } } } return memo[n]; } }
1 上面的二维数组空间有点多余了,可以不用那个空间。
2 从最小的字符串(0,0) 开始检查,如果是true,代表是这个字符串在字典中;然后再根据字典,看看可以延伸到哪几个位子,标注为true,直到字典检查结束。之后,查看下个标注为true的位子,再根据字典,把可以延伸的继续找到。看看最后能不能到达n-1。
3 这是从dfs 一步步演化到dp,只适用于这道题目的最简便算法了。
public class Solution { public boolean wordBreak(String s, Set<String> dict) { boolean[] canBreak = new boolean[s.length()+1]; canBreak[0] = true; for(int i=0; i<s.length(); i++){ if(canBreak[i] == false){ continue; } for(String dictS : dict){ int len = dictS.length(); int end = i + len; if(end > s.length()){ continue; } if(s.substring(i, end).equals(dictS)){ canBreak[end] = true; } } } return canBreak[s.length()]; } }