题目及测试
package pid140;
/*单词拆分 II给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明：分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
["cats and dog","cat sand dog"
]示例 2：输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
["pine apple pen apple","pineapple pen apple","pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。示例 3：输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]*/import java.util.ArrayList;
import java.util.List;public class main {public static void main(String[] args) {String [] testTable = {"catsanddog","applepenapple","catsandog"};List<List<String>> testTable2=new ArrayList<List<String>>();List<String> list=new ArrayList<>();list.add("cat");list.add("cats");list.add("and");list.add("sand");list.add("dog");testTable2.add(list);list=new ArrayList<>();list.add("apple");list.add("pen");testTable2.add(list);list=new ArrayList<>();list.add("cats");list.add("dog");list.add("sand");list.add("and");list.add("cat");testTable2.add(list);for(int i=0;i<testTable.length;i++){test(testTable[i], testTable2.get(i));}}private static void test(String ito,List<String> ito2) {Solution solution = new Solution();List<String> rtn;long begin = System.currentTimeMillis();System.out.print(ito); System.out.println();for(String str:ito2){System.out.print(str+" "); }System.out.println();//开始时打印数组rtn= solution.wordBreak(ito,ito2);//执行程序long end = System.currentTimeMillis(); System.out.println("rtn=" );for(String str:rtn){System.out.println(str+" "); }System.out.println();System.out.println("耗时：" + (end - begin) + "ms");System.out.println("-------------------");}}
解法1（不成功，应该是对的，超时）
建立一个List<List<String>> lists，lists[i] 代表[0,i]的字符串，拆分后的字符串数组。
之前的[0,j]，新的单词(j,i]，每次将之前的lists[j] 加上空格，加上符合要求的s.subString(j+1,i+1)
package pid140;import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;public class Solution {public List<String> wordBreak(String s, List<String> wordDict) {int length=s.length();if(length==0){return new ArrayList<String>();}Set<String> set=new HashSet<>(wordDict);// lists[i] 代表[0,i]的字符串，拆分后的字符串数组List<List<String>> lists=new ArrayList<>();for(int i=0;i<length;i++){lists.add(new ArrayList<>());}for(int i=0;i<length;i++){List<String> list=lists.get(i);for(int j=-1;j<i;j++){// 之前的[0,j]，新的单词(j,i]// j=-1,[0,-1],(-1,i]// j=0,[0,0],(0,i]// j=1,[0,1],(1,i]// j=i-1,[0,i-1],(i-1,i]if(j==-1){if(set.contains(s.substring(0, i+1))){list.add(s.substring(0, i+1));}}else{if(lists.get(j).size()>0&&set.contains(s.substring(j+1, i+1))){for(String str:lists.get(j)){list.add(str+" "+s.substring(j+1, i+1));}}}}} return lists.get(length-1);}}
解法2（别人的）
这个方法背后的想法是对于给定的问题（s），它可以被拆分成子问题 s1s1s1 和 s2s2s2 。如果这些子问题分别都能满足条件，那么整个文字 s 也可以满足。比方说， "catsanddog" 可以被拆分成子字符串 "catsand" 和 "dog" 。子问题 "catsand" 进一步可以被拆分成 "cats" 和 "and" ，它们分别都是字典的一部分，所以 "catsand" 也是满足条件的。递归回来，因为 "catsand" 和 "dog" 分别都满足要求，所以原字符串 "catsanddog" 也符合要求。
现在，我们来考虑 dp 数组如何求出。我们使用长度为 n+1n+1n+1 的数组 dp ，其中 n 是给定字符串的长度。 dp[k] 被用来存储用 s[0:k?1]可被拆分成合法单词的句子。我们同事用两个指针 i 和 j ，其中 i 表示子字符串 s′ 的长度（s′ 是 s 的一个前缀）， j 表示 s′ 的拆分位置，即拆分成 s′(0,j) 和 s′(j+1,i) 。
为了求出 dp 数组，我们将 dp[0] 初始化为空串。我们以 i 为结尾表示的子字符串的所有前缀，通过指针 j 将 s 拆分成 s1′ 和 s2′ 。为了求出dp[i] ，我们检查所有 dp[j] 包含的所有非空字符串，也就是所有能形成 s1′ 的句子。如果存在，我们进一步检查 s2′ 是否在字典里，如果两个条件都满足，我们将子字符串 s2′ 添加到所有 s1′ 的句子的后面（这些句子已经保存在了 dp[j] 里面），并将这些新形成的句子保存进（dp[i]）。最终， dp[n] （n 是给定字符串 s 的长度）里面保存了所有可以得到完整字符串 s 的所有句子。
public class Solution {public List<String> wordBreak(String s, Set<String> wordDict) {LinkedList<String>[] dp = new LinkedList[s.length() + 1];LinkedList<String> initial = new LinkedList<>();initial.add("");dp[0] = initial;for (int i = 1; i <= s.length(); i++) {LinkedList<String> list = new LinkedList<>();for (int j = 0; j < i; j++) {if (dp[j].size() > 0 && wordDict.contains(s.substring(j, i))) {for (String l : dp[j]) {list.add(l + (l.equals("") ? "" : " ") + s.substring(j, i));}}}dp[i] = list;}return dp[s.length()];}
}