Leetcode 140 word break II - need to debug the code and then understand the brute force solution - May 6, 2018 - 9:51 PM

Leetcode 140 Word break II

I like to study the algorithm based on the following blog: 

https://blog.csdn.net/linhuanmars/article/details/22452163

I like to go over the analysis word by word first. 

这道题目要求跟Word Break比较类似，不过返回的结果不仅要知道能不能break，如果可以还要返回所有合法结果。
一般来说这种要求会让动态规划的效果减弱很多，因为我们要在过程中记录下所有的合法结果，中间的操作会使得
算法的复杂度不再是动态规划的两层循环，因为每次迭代中还需要不是constant的操作，最终复杂度会主要取决于
结果的数量，而且还会占用大量的空间，因为不仅要保存最终结果，包括中间的合法结果也要一一保存，否则后面
需要历史信息会取不到。所以这道题目我们介绍两种方法，一种是直接brute force用递归解，另一种是跟Word Break
思路类似的动态规划。

****brute force解法****
对于brute force解法，代码比较简单，每次维护一个当前结果集，然后遍历剩下的所有子串，如果子串在字典中
出现，则保存一下结果，并放入下一层递归剩下的字符。思路接近于我们在N-Queens这些NP问题中经常用到的套路

public ArrayList<String> wordBreak(String s, Set<String> dict) {  
    ArrayList<String> res = new ArrayList<String>();  
    if(s==null || s.length()==0)  
    {
        return res;  
    }
        
    helper(s,dict,0,"",res);  
    
    return res;  
}  

private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res)  
{  
    if(start >= s.length())  
    {  
        res.add(item);  
        return;  
    }  
    
    StringBuilder str = new StringBuilder();  
    
    for(int i = start;i < s.length();i++)  
    {  
        str.append(s.charAt(i));  
        
        if(dict.contains(str.toString()))  
        {  
            String newItem = item.length() > 0? (item + " " + str.toString()) : str.toString();  
            
            helper(s, dict, i + 1, newItem, res);  
        }  
    }  
}  

****动态规划的解法****
接下来我们列出动态规划的解法，递推式跟Word Break是一样的，只是现在不只要保存true或者false，还需要保存
true的时候所有合法的组合，以便在未来需要的时候可以得到。不过为了实现这点，代码量就增大很多，需要一个数据
结构来进行存储，同时空间复杂度变得非常高，因为所有中间组合都要一直保存。时间上还是有提高的，就是当我们需要
前面到某一个元素前的所有合法组合时，我们不需要重新计算了。不过最终复杂度还是主要取决于结果的数量。

code is added here...

可以看出，用动态规划的代码复杂度要远远高于brute force的解法，而且本质来说并没有很大的提高，甚至空间上还是
一个暴涨的情况。所以这道题来说并不是一定要用动态规划，有一个朋友在面Amazon时遇到这道题，面试官并没有要求
动态规划，用 brute force 即可，不过两种方法时间上和空间上的优劣还是想清楚比较好，面试官可能想听听理解。
实现的话可能主要是递归解法。

还有一点需要指出的是，上面的两个代码放到 LeetCode 中都会超时，原因是LeetCode中有一个非常tricky的测试case，
其实是不能break的，但是又很长，出现大量的记录和回溯，因此一般通过这个的解法是把Word Break先跑一遍，判断是
不是能break，如果可以再跑上面的代码。这样做法其实比较傻，但是为了过这个只能这样了，这一点我觉得LeetCode没
必要把超时设得这么严格，实际意义不大，只是把AC率给拉了下来哈。

Julia's comment: what is tricky test case here?

I need to run C# code and understand the brute force solution first.