[leetcode] Word Break

这题可以用Dynamic programming 解答.
subproblem[i] 表示 0到i的substring 能不能被间开..
subproblem[i] = subproblem[j] && substring[j+1,i+1) is in dictionary

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

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