[LeetCode]Word Break II

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

然后考虑到我们在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)))

代码如下：