00回溯困难 LeetCode140. 单词拆分 II NC182 单词拆分(二)

140. 单词拆分 II

描述

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

分析

回溯思想
从头开始向后遍历，截取字符串，判断字符串是否在字典集合中出现，存在则向下递归(下层的起始是从上层的单词后面的那个字符开始的)，若不存在跳过，继续向后遍历，直到遍历结束。

• 递归结束条件：遍历的起点等于字符串s的长度
• 使用两个全局List，一个存储每层确定的单词，一个存储结果“句子”。

class Solution {
    List<String> res;
    List<String> dic;
    List<String> sb;
    public List<String> wordBreak(String s, List<String> wordDict) {
        res = new ArrayList<>();
        sb = new ArrayList<>();
        dic = wordDict;
        backTrace(s,0);
        return res;
    }

    public void backTrace(String s, int index){
        if(index == s.length()){
            String tmp = "";
            for(int i = 0; i < sb.size()-1; i++){
                tmp += sb.get(i) + " ";
            }
            tmp += sb.get(sb.size()-1);
            res.add(tmp);
            return;
        }
        for(int i = index; i < s.length(); i++){
            String str = s.substring(index,i+1);
            if(dic.contains(str)){
                sb.add(str);
                backTrace(s,i+1);
                sb.remove(sb.size()-1);
            }
        }
    }
}