[LeetCode 140] Word Break II (Ha

Solution

1. 因为要求所有解，所以不能像139一样找到一组解就返回，需要找到所有解。
2. 同样需要使用记忆递归： Map<String, List<String>> 表示该String，能分解且能够在wordList中找到的substring。
3. 递归函数，返回List<String> 即为找到的结果
   • base case： 当startIndex == endIndex, return null, 代表的情况是 例如 cat， startIndex已经走到了3，cat已经全部扫描完成，其右边不能再继续递归了，所以返回空。
   • 再判断 MAP中是否已有记录，如果有，则直接返回记录值
   • 如果都不满足，那么开始对当前substring进行处理

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        if (wordDict == null || wordDict.size () == 0) {
            return new ArrayList<String> ();
        }
        
        Map<String, List<String>> tracker = new HashMap<> ();
        Set<String> wordSet = new HashSet<> (wordDict);
        return wordBreakHelper (s, wordSet, 0, s.length (), tracker);
        
    }
    
    private List<String> wordBreakHelper (String str, 
                            Set<String> wordDict, 
                            int start, 
                            int end, 
                            Map<String, List<String>> tracker) {
        
        if (tracker.containsKey (str.substring (start, end)))
            return tracker.get (str.substring (start, end));
        
        // base case: if it is a null string, return null
        if (start == end)
            return null;
        
        List<String> result = new ArrayList<> ();
        
        for (int i = start; i < end; i++) {
            String subTemp = str.substring (start, i + 1);
            List<String> partialResult = new ArrayList<> ();
                
            if (wordDict.contains (subTemp)) {
                System.out.println ("--- contains:   " + subTemp);
                partialResult = wordBreakHelper (str, wordDict, i + 1, end, tracker);
                
                // partial result == null 对应的是已经全部走完了，cat，startIndex已经走到了t后面，相当于找到整个cat，所以将其放入result
                if (partialResult == null) {
                    result.add (subTemp);
                    System.out.println (subTemp + ": add to result");
                } else {
                    // 不为null的时候，那么就把subTemp与所有的partialResult进行组合，就是解
                    for (String subTempNext : partialResult) {
                        
                        result.add (subTemp + " " + subTempNext);
                        System.out.println ("------" + subTemp + " " + subTempNext);
                    }
                }
            } 
        }
        
        tracker.put (str.substring (start, end), result);
        return result;
    }
}