## Saturday, August 9, 2014

### 包子IT面试培训 助你拿到理想的offer!

Note: 本篇只讨论算法的时间复杂度，不涉及算法的空间复杂度。:)

『简单的时间复杂度计算』

『相对复杂的时间复杂度计算』

Problem:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.  Return one such possible sentences.

s = "catsanddog", dict = ["cat", "cats", "and", "dog"], return “cats and dog"；

(Leetcode word break II 简化版)

Clarification

Q: What to return if s can’t be splitted into words in dict? A: Return NULL;
Q: What if there are multiple ways of splitting s? A: Return one split solution is fine;
Q: What if S is null/empty string? A: Return NULL;
So on and so forth..

Code in first pass:
public String wordBreak(String s, Set<String> dict) {
if (s == null || s.isEmpty()) {
return s;
}
List<String> solution = new ArrayList<String>();
boolean ret = wordBreakHelper(s, dict, solution);
if (!ret) {
return null;
}

//from apache commons lang
return StringUtils.join(solution, " ");
}

private boolean wordBreakHelper(String s, Set<String> dict, List<String> solution) {
if (dict.contains(s)) {
return true;
}
for(int index = 1; index < s.length(); ++index) {
String left = s.substring(0, index);
if (dict.contains(left)) {
boolean ret = wordBreakHelper(s.substring(index), dict, solution);
if (ret) {
return ret;
} else {
solution.remove(solution.size() - 1);
}
}
}
return false;
}

Code in second pass:

private boolean wordBreakHelper(String s, Set<String> dict, Set<String> unsplitableSet, List<String> solution) {
if (dict.contains(s)) {
return true;
}
if (unsplitableSet.contains(s)) {
return false;
}
for(int index = 1; index < s.length(); ++index) {
String left = s.substring(0, index);
if (dict.contains(left)) {
boolean ret = wordBreakHelper(s.substring(index), dict, unsplitableSet, solution);
if (ret) {
return ret;
} else {
solution.remove(solution.size() - 1);
}
}
}
return false;
}