139. Word Break - medium

这道题做的很值。
题不难，但是考察点很明确。
做DP的最大问题就是用递归，忘记用table来写。然后不停重复计算，exponential的运算增长，直接就爆了。这道题之所以是medium估计也是考这个的。

这个是典型的时间会爆掉的代码：

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0)    throw new IllegalArgumentException("Invalid Input");
        int len = s.length();
        for(int i=1; i<=s.length(); i++) {
            String str = s.substring(0,i);
            if(wordDict.contains(str) && (i==len || wordBreak(s.substring(i,len), wordDict)))
                return true;
        }
        return false;
    }
}

用DP做的代码：
没什么好说的。

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] mem = new boolean[s.length() + 1];
        mem[0] = true;
        for (int i=1; i<=s.length(); i++) {
            for (int j=0; j<i; j++) {
                if (mem[j] && wordDict.contains(s.substring(j,i))) {
                    mem[i] = true;
                    break;
                }
            }
        }
        return mem[s.length()];
    }
}

重复计算是DP里面用递归的大忌，这种一般要用top-down，memory做table。
不能重复计算，不能重复计算，不能重复计算！重要的事情说三遍！
============
much more effective at night.
How to block the sunshine during the day?
I will try to coding in my closet tomorrow : )