Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
动态规划的思想，分别考虑n+1个划分点是否是breakable的，当前i位置是否可以breakable由breakable[j]和s.substring(j,i)是否存在于dict中决定，即breakable[i]=
breakable[j]&dict.contains(s.substring(j,i)) 其中j∈[0,i-1].
public class Solution { public boolean wordBreak(String s, Set<String> dict) { int size = s.length(); boolean[] breakable = new boolean[size+1]; breakable[0] = true; for(int i=1;i<=size;i++) { for(int j=0;j<i;j++) { if(breakable[j]&&dict.contains(s.substring(j,i))) { breakable[i] = true; break; } } } return breakable[size]; } }
原文：http://www.cnblogs.com/mrpod2g/p/4356981.html