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"
.
A:
public class Solution { public boolean wordBreak(String s, Set<String> dict) { // treat the whole string, as appending each letter at end int n = s.length(); boolean[] blnBreak = new boolean[n+1]; blnBreak[0] = true;// the first one is always true, before first char in s for(int i =0;i<n;i++){ int j = i; while(j>=0 ){ String lastStr = s.substring(j,i+1); // including ith position if(blnBreak[j] && dict.contains(lastStr) ){ blnBreak[i+1] = true; break; }else{ // not find match j--; } } } return blnBreak[n]; } }
Mistakes:
1:在 blnBreak里,是用了n+1的size,但是,实际设置的时候, 用的i,还是0到 n-1.
因此,最后的一个,总是没有设置好。
因此应该用, blnBreak[i+1] = true; 而不是blnBreak[i] = true;
--------上面的是记录了前面可以分割的,同样,我们可以每次取下前面的一部分来。后面的递归查找***********
public class Solution { public boolean wordBreak(String s, Set<String> wordDict) { if(s==null || s.length()==0) return true; int[] canBreak = new int[s.length()]; // canBreak[i] == 0 --> tested, 1--> can break from this position(inclusive) till end, -1-->cannot return helper(s, wordDict, canBreak, 0) > 0; } private int helper(String s, Set<String> dict,int[] canBreak, int start ){ int n = s.length(); // start is index, thus always valid if( canBreak[start] !=0 ) return canBreak[start]; for(int end = start; end <n;end++){ String frontStr = s.substring(start,end+1); if(dict.contains(frontStr)){ if( end == n-1 || helper(s,dict,canBreak,end+1)>0){ canBreak[start] = 1; return canBreak[start]; } } } canBreak[start] = -1; return canBreak[start]; } }
No comments:
Post a Comment