https://leetcode-cn.com/problems/word-break/
1. 字符串S = {s1,s2,s3,s4...sn}
字典set = {S1,S2,S3....Sn}
2. 子问题划分
S = S1 + S2
S1 = S11 +S12
S2 = S21 + S22
如果S1被包含在字典中，并且S2也被包含在字典中，则S是可拆分的
3. 边界
S1 == S 也就是说 S2 = NULL
4. 程序：
设置一个Boolean数组，存储第i个字母开头的字符串是否是可拆分的
例：“appledog” {"app","apple","dog"}
public boolean helper(String s,Set<String> set,int start,Boolean[] mem){ if(start == s.length()){ return true; } if(mem[start] != null){ return mem[start]; } for(int end = start + 1; end <= s.length(); end++){ if(set.contains(s.substring(start,end)) && helper(s,set,end,mem)){ mem[start] = true; return true; } } mem[start] = false; return false; } public boolean wordBreak(String s, List<String> wordDict) { Set<String> set = new HashSet<String>(wordDict); Boolean[] mem = new Boolean[s.length()]; return helper(s,set,0,mem); }
原文：https://www.cnblogs.com/da-peng/p/11792554.html