http://baozitraining.org/blog/calculate-hard-runtime-complexity-in-recursive-solution/
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"；
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 fort.
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)) { solution.add(s); return true; } for(int index = 1; index < s.length(); ++index) { String left = s.substring(0, index); if (dict.contains(left)) { solution.add(left); boolean ret = wordBreakHelper(s.substring(index), dict, solution); if (ret) { return ret; } else { solution.remove(solution.size() - 1); } } } return false; }
时间复杂度分析
这样的解法看起来一目了然，对于每一个字符串，分成左右子字符串，查左子串、递归右子串（想想为什么不需要递归左子串）。 那么这个算法的时间复杂度是多少呢？ 这个复杂度的计算并非那么容易一眼看出，因为解法中的循环内有递归，而每一个递归中又存在循环。所以数嵌套循环数的方法并不好用。因此我们拿一个具体的例子来看：
假设字符串s是abcde; 那么算法变化如下：
当index = 1, 字符串分为左串a和右串bcde，如果a不在字典中，那么这个拆分不成立，情况简化；如果a恰好在字典中，那么算法有两种选择，一种选择是将a放入结果集，然后递归bcde，另一种是不选择a作为完整单词，而是作为单词的一部分去试探下一个index。
当index = 2, 由于index = 1时产生了两种情况：a bcde 和 abcde。 对于a bcde的情况，由于算法递归bcde，和index = 1的情况类似，如果b在字典中，那么会演化出两种情况：a b cde; a bcde; 对于abcde的情况，如果ab在字典中，那么会演化出两种情况：ab cde; abcde;
写到这里，大家应该看得出来，对于每一个index上的字母，是否选择该字母作为单词结束的决定会产生两种可能，而且是层层叠加。因此该算法的复杂度就是2的n次方。
上面的写法虽然思路简单，但是不可避免的进行了很多重复运算。比如cde这个单词至少会被a b cde 和ab cde这两种拆分方法共同计算，如果我们能利用一个额外的集合记录之前的计算结果，那么算法的复杂度会大大下降。
private boolean wordBreakHelper(String s, Set<String> dict, Set<String> unsplitableSet, List<String> solution) { if (dict.contains(s)) { solution.add(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)) { solution.add(left); boolean ret = wordBreakHelper(s.substring(index), dict, unsplitableSet, solution); if (ret) { return ret; } else { solution.remove(solution.size() - 1); } } } unsplitableSet.add(s); return false; }
既然上面的算法避免了相同子串的重复计算，那么以上这个算法的时间复杂度是多少呢？ 考虑到所有重复计算已经被排除，那么我们不防穷举所有可能的计算尝试，同样以abcde为例：
以a开头的尝试：a, ab, abc, abcd, abcde,
以b开头的尝试：b, bc, bcd, bcde,
以c开头的尝试：c, cd, cde,
…
显然所有的计算尝试是n平方的复杂度（n位字符串长度），考虑到所有的尝试只计算一次（算法中的unsplitableSet起到的作用），因此上面的时间复杂度位n的2次方。
