Massive Algorithms: Word Break Related

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次方。

Word Break Related

时间复杂度分析

Labels

Popular Posts