[LeetCode]Word Break II

首先是backtracking的解法，搜所有可能的，大数据会超时，代码如下：

	public class Solution {
	public List<String> wordBreak(String s, Set<String> dict) {
	List<String> res = new ArrayList<String>();
	if (s == null)
	return res;
	int len = s.length();
	String temp = "";
	backtracking(res, s, dict, 0, temp);
	return res;
	}
	private void backtracking(List<String> res, String s, Set<String> dict, int index, String temp) {
	int len = s.length();
	if (len == index) {
	res.add(temp);
	return;
	}
	for (int i = index; i < len; i++) {
	if (dict.contains(s.substring(index, i + 1))) {
	String aux = temp.length() == 0? temp + s.substring(index, i + 1): temp + " " + s.substring(index, i + 1);
	backtracking(res, s, dict, i + 1, aux);
	}
	}
	}
	}

view raw word break II v-2.java hosted with ❤ by GitHub

然后考虑到我们在Word Break中过的方法，我们可以把boolean的array改成arraylist的arraylist， 假设第i + 1个存的是k1，k2，代表k1到i和k2到i是在字典里的，并且前k1个和k2个字符组成的string也是在字典里的。然后通过这个arraylist来重构答案，可以减掉很多枝，时间复杂度是O(N^2 + k)，k是最后可行的break，用f[i]表示前i个字符有多少种break的方法，DP方程：

• f[i] = {j1,j2....} 其中(f[jk] && dict.contains(s.substring(jk, i + 1)))

代码如下：

	public class Solution {
	public List<String> wordBreak(String s, Set<String> dict) {
	List<String> res = new ArrayList<String>();
	if (s == null || dict == null)
	return res;
	int len = s.length();
	ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
	arr.add(new ArrayList<Integer>());
	arr.get(0).add(-1);
	for (int i = 0; i < len; i++) {
	arr.add(new ArrayList<Integer>());
	for (int j = i; j >= 0; j--) {
	if (arr.get(j).size() != 0 && dict.contains(s.substring(j, i + 1)))
	arr.get(i + 1).add(j);
	}
	}
	rebuild(res, arr, s, "", len);
	return res;
	}
	private void rebuild(List<String> res, ArrayList<ArrayList<Integer>> arr, String s, String temp, int index) {
	if (index == 0) {
	res.add(temp);
	return;
	}
	ArrayList<Integer> list = arr.get(index);
	int len = list.size();
	for (int i = 0; i < len; i++) {
	int start = list.get(i);
	String substring = s.substring(start, index);
	rebuild(res, arr, s, temp.length() == 0? substring: substring + " " + temp, start);
	}
	}
	}

view raw word break II v-1.java hosted with ❤ by GitHub