🌕 🌗 140. 单词拆分 II

难度: 🌕 🌗

问题描述

---

解法

class Solution {
    List<String> res;
    public List<String> wordBreak(String s, List<String> wordDict) {
        // 思路：
        // dp + 回溯
        // dp 判断以那些节点作为右边界，可以拆分
        // 回溯 得到满足条件的集合
        // 可以将满足条件的起始单词作为查找入口，依次以这部分单词作为回溯的入口
        res = new ArrayList<>();
        int len = s.length();
        boolean[] dp = new boolean[len];
        List<String> list = new ArrayList<>();
        for(int i = 0; i < len; i ++) {
            for(String str: wordDict) {
                int size = str.length();
                if(i >= size - 1) {
                    String cur = s.substring(i - size + 1, i + 1); // 左闭右开
                    if(cur.equals(str) && (i == size - 1 || dp[i - size])) {
                        dp[i] = true;
                        // System.out.println(i);
                        // 判断是否是起始单词
                        if(i == size - 1) {
                            list.add(cur);
                        }
                    }
                }
            }
        }
        if(!dp[len - 1]) {
            return res; // 说明一个满足条件的情况也不存在
        }
        // 回溯
        HashSet<String> set = new HashSet<>(wordDict);
        for(String first : list) {
            LinkedList<String> path = new LinkedList<>();
            path.addLast(first);
            mySol(s, len, set, dp, first.length(), path);
        }
        return res;
    }

    private void mySol(String s,int len, HashSet<String> set, boolean[] dp, int index, LinkedList<String> path) {
        // System.out.println(index + " : " + getStr(path));
        // 递归终止条件
        if(index == len) {
            res.add(getStr(path));
            return;
        }
        // index < len - 1 还需要继续添加单词
        for(int i = index; i < len; i ++) {
            if(dp[i]) {
                String tmp = s.substring(index, i + 1); // [index, i]
                if(set.contains(tmp)) {
                    // 说明肯定可以拆分
                    path.addLast(tmp);
                    mySol(s, len, set, dp, i + 1, path);
                    path.removeLast();
                }
            }
        }
    }

    private String getStr(LinkedList<String> path) {
        StringBuilder sb = new StringBuilder();
        for(String cur : path) {
            sb.append(cur).append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
} 

---

输出