算法——单词拆分 II

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
链接: leetcode.

解题思路：

首先用暴力的深度优先搜索，然后发现对部分测试用例会超时，所以需要对搜索进行剪枝。一般的剪枝手段都是记忆化一种状态的结果，然后当下次搜索到这一状态时防止重复计算，这样基本能将时间复杂度降到O(N)。
深度优先搜索基本使用这一模板，传入一个temp结果，每次递归到底部之前，给temp增加值，然后记得需要回溯，也就是去除当前状态下增加的值。
这里的剪枝我是这么考虑的，如果当前位置往后递归后无法增加结果，说明这个位置之后的字符串不能被拆分，所以，其他分支搜索到当前位置时，就没必要往下计算，通过一个hash表，记录下这个位置的状态，然后后来的分支检测到这个位置的状态，直接返回。

// created by lippon

class Solution {

    List<String> res = new ArrayList<>();

    Map<String, Boolean> wd = new HashMap<>();

    Map<Integer, Boolean> men = new HashMap<>();

    public List<String> wordBreak(String s, List<String> wordDict) {

        for(String w : wordDict) wd.put(w, true);

        dfs(0, new StringBuilder(), s);

        return res;

    }

    public void dfs(int cur, StringBuilder temp, String s) {

    	// 搜索到了底部

        if(cur == s.length()) {

            if(temp.length() > 0) {

                // 添加结果

                temp.deleteCharAt(temp.length() - 1);

                res.add(temp.toString());

            }

            return ;

        }

		// 剪枝，查看当前位置后的字符串时候不能被拆分，如果不能，直接返回

        if(men.getOrDefault(cur, false)) return;

        // 记录这次dfs时的结果数

        int len = res.size();

        for(int i = cur + 1; i <= s.length(); i++) {

            String word = s.substring(cur, i);

            if(wd.containsKey(word)) {

                StringBuilder nt = new StringBuilder(temp);

                temp.append(word);

                temp.append(" ");

                dfs(i, temp, s);

				// 回溯

                temp = nt;

            }

        }

		// 如果结果没有增加，说明该位置不能产生答案，进行记忆

        if(len == res.size()) men.put(cur, true);

    }

}

算法——单词拆分 II的相关教程结束。