Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []


思路：剪裁一下，用剩下的一截去查找

class Solution {
  //https://leetcode.com/problems/word-break-ii/discuss/44167/My-concise-JAVA-solution-based-on-memorized-DFS
  public List < String > wordBreak(String s, List < String > wordDict) {
    return backtrack(s, wordDict, new HashMap < String, List < String >> ());
  }
    
    //先找cat，找到了，在剩下的anddog里找cat cats。。。, 没有，找and，找到了。在dog里找cat cats。。。，知道全部找到以后，从内而外append起来
  // backtrack returns an array including all substrings derived from s.
  public List<String> backtrack(String s, List< String > wordDict, Map < String, List<String>> mem) {
    //已经添加完了的话，就拿出来
    if (mem.containsKey(s)) return mem.get(s);
      
    List <String> result = new ArrayList < String > ();
      
    for (String word: wordDict) {
     System.out.println("word = " + word);
      
      if (s.startsWith(word)) {
        System.out.println("s = " + s); 
        //剪裁一下，用剩下的一截去查找          
        String next = s.substring(word.length()); 
        System.out.println("剩下的一截next = " + next);
        //递归结束，此时直接添加这个单词
        if (next.length() == 0) {result.add(word);
                    
                                }
        else
        //sub是接下来的单词计算出来的结果，和之前的word拼接后添加
          for (String sub: backtrack(next, wordDict, mem)) {
              System.out.println("sub = " + sub);
              result.add(word + " " + sub);
          }
      }
    
    //放到map中去重
    System.out.println("递归好像结束了");
    System.out.println("result = " + result);
    mem.put(s, result);
      
    System.out.println(" ");
  }
      return result;
  }
}