这道题做的很值。
题不难，但是考察点很明确。
做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 : )
