Leetcode 140 word break II - study one blog how to handle super long test case causing TLE error.

Leetcode 140 word break II

Leetcode 140. Work break II

I like to study the coding blog:
http://www.cnblogs.com/yrbbest/p/4438816.html

I like to go over the notes word by work, customize to fit for my reading style first. 

求所有解集的题目可以用用DFS + Backtracking。在Word Ladder II里我们这样做，在这里我们依然这样做。
现在 DFS 往往伴随 Backtracking，有个超长的case需要提前判断能否 word break，所以还要用带一部分
Word Break I 里面的代码。使用了一个 StringBuilder 来回溯加入的单词以及空格。这回时间
复杂度是真的O(2^n)了。

Time Complexity - O(2n)， Space Complexity - O(2n)

Java code:

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<>();
        
        if(s == null || wordDict == null)
        {
            return res;
        }
        
        StringBuilder sb = new StringBuilder();
        if(canWordBreak(s, new HashSet<String>(wordDict)))      //find out if we can word break
        {
            findAllWordBreak(res, sb, s, wordDict);
        }
            
        return res;
    }
    
    private void findAllWordBreak(List<String> res, StringBuilder sb, String s, Set<String> wordDict) {
        if(s.length() == 0) {
            res.add(sb.toString().trim());
            return;
        }
        
        for(int i = 1; i <= s.length(); i++) {
            String frontPart = s.substring(0, i);
            String backPart = s.substring(i, s.length());
            
            if(wordDict.contains(frontPart)) {
                sb.append(frontPart);
                sb.append(" ");
                findAllWordBreak(res, sb, backPart, wordDict);
                sb.setLength(sb.length() - 1 - frontPart.length());
            }
        }
    }
    
     private boolean canWordBreak(String s, Set<String> wordDict) {     //Word Break I
        if(s == null || wordDict == null)
        {
            return false;
        }
            
        if(s.length() == 0)
        {
            return true;
        }
        
        for(int i = 1; i <= s.length(); i++) {
            String frontPart = s.substring(0, i);
            String backPart = s.substring(i, s.length());
            
            if(wordDict.contains(frontPart)) {
                if(canWordBreak(backPart, wordDict))
                {
                    return true;
                }
                
                wordDict.remove(frontPart);
            }
        }
        
        return false;
    }
}

corrections: Line 6, word by word, not work by work.