leetcode--12. 动态规划 II

题目：
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
给定一个字符串s和一个单词词典，在s中添加空格以构造一个句子，其中每个单词都是一个有效的字典单词。
返回所有这些可能的句子。
For example, given
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].

A solution is["cats and dog", "cat sand dog"]

思路：
动态规划思想，用map把已经求得的结果存起来，避免重复劳动 (有待补充)
（牛客网给定的结果按固定顺序输出，暂时做不到）

import java.util.*;

public class Solution{
    /*
     * 动态规划思想，用map把已经求得的结果存起来，避免重复劳动
     */
    public ArrayList<String> wordBreak(String s, Set<String> wordDict) {
        return DFS(s, wordDict, new HashMap<String, ArrayList<String>>());
    }
 
    private ArrayList<String> DFS(String s, Set<String> wordDict, HashMap<String, ArrayList<String>> map) {
        if (map.containsKey(s))
            return map.get(s);
        ArrayList<String> res = new ArrayList<String>();
        if (s.length() == 0){
            res.add("");
            return res;
        }
        for (String subStr : wordDict) {
            if (s.startsWith(subStr)) {
                for (String str : DFS(s.substring(subStr.length()), wordDict, map)) {
                    res.add(subStr + (str == "" ? "" : " ")+ str);
 
                }
 
            }
        }
        map.put(s, res);
        return res;
    }
}