The tricky part is to come up with a way to save previous bad strings so that save some time for the code… which I used the hash set and made it global for each recursive call.
The other is be NOT scared by the question, just do recursively analyze and solve it level by level…
public class Solution {
HashSet<String> map = null;
public ArrayList<String> wordBreak(String s, Set<String> dict) {
ArrayList<String> res = new ArrayList<String>();
if(s == null || s.length() == 0)
return res;
map = new HashSet<String>();
res = recBreak(s, dict);
return (res != null)?res:new ArrayList<String>();
}
private ArrayList<String> recBreak(String s, Set<String> dict){
if(s==null || map.contains(s))
return null;
ArrayList<String> list = new ArrayList<String>();
ArrayList<String> temp = null;
for(int i =1; i<= s.length(); i++){
temp = new ArrayList<String>();
String str = s.substring(0, i);
if(dict.contains(str)){
if(i < s.length())
temp = recBreak(s.substring(i, s.length()), dict);
if(temp != null){
if(temp.size() == 0)
list.add(str); //test case ["a"]
else{
for(int j = 0; j< temp.size(); j++){
list.add(str+" "+temp.get(j));
}
}
}else{
map.add(s.substring(i, s.length()));
}
}
}
return (list.size() > 0)?list:null;
}
}
1 条评论:
public class Solution {
Set previous = new HashSet();
public List wordBreak(String s, Set dict) {
if(s == null || previous.contains(s)){
return new ArrayList();
}
List results = new ArrayList();
for(int j = 1; j <= s.length(); j++){
String curPrefix = s.substring(0, j);
if(dict.contains(curPrefix)){
if(j == s.length()){
results.add(curPrefix);
}else{
List preResults = wordBreak(s.substring(j, s.length()), dict);
if(preResults.size() > 0){
for(String result : preResults){
results.add(curPrefix + " " + result);
}
}else{
previous.add(s.substring(j, s.length()));
}
}
}
}
return results;
}
}
Simpler version. Update the tricky part: save previous invalid strings to save time; plus remember the extreme case that the only string is the entire string, need a if condition to process; be careful of what will return, in the code above, return a list size of zero, never return null.
发表评论