algo/di-er-zhan-a01c6/dong-tai-g-a223e/dong-tai-g-f0a05/

[giscus[bot]]

algo/di-er-zhan-a01c6/dong-tai-g-a223e/dong-tai-g-f0a05/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 139. Word ...

https://labuladong.gitee.io/algo/di-er-zhan-a01c6/dong-tai-g-a223e/dong-tai-g-f0a05/

[RomeoFourier]

dp数组法、Java：

    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            int length = s.length();
            boolean[] dp = new boolean[length];
            for (int i = 0; i < length; i++) {
                if (i == 0 || dp[i - 1]) {
                    for (String word : wordDict) {
                        int l = word.length();
                        if (i + l <= length && !dp[i + l - 1] && s.substring(i, i + l).equals(word)) {
                            dp[i + l - 1] = true;
                        }
                    }
                }
            }
            return dp[length - 1];
        }
    }

[xixi1998]

单词拆分1，还是超时呢

[xixi1998]

是我第二个if 忘记return了

[ZeplerFu]

有个小笔误：单词拆分I中定义及优化dp函数时，应该是boolean dp不是int dp

[HCWGH]

单词拆分I,这样写的效率更高一点

class Solution {
    Map<Integer, Boolean> back = new HashMap<Integer, Boolean>();

    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict, 0);
    }


    public boolean dfs(String s, List<String> wordDict, int index) {
        //匹配完成
        if (index == s.length()) {
            return true;
        }
        if (back.containsKey(index)) {
            return back.get(index);
        }
        boolean res = false;
        for (int i = 0; i < wordDict.size(); i++) {
            String word = wordDict.get(i);
            int length = word.length();
            if (length > s.length() - index) {
                continue;
            }
            //当前单词已经与s的部分配，有两种选择,选择与其匹配或者不选择与其匹配
            if (word.equals(s.substring(index, index + length))) {
                if (dfs(s, wordDict, index + length)) {
                    res = true;
                    break;
                }
            }
        }
        back.put(index, res);
        return res;
    }
}

[HCWGH]

单词拆分I.去掉for循环

class Solution {
    Map<Integer, Boolean> back = new HashMap<Integer, Boolean>();

    public boolean wordBreak(String s, List<String> wordDict) {
        return dfs(s, wordDict, 0, 0);
    }


    public boolean dfs(String s, List<String> wordDict, int index, int dIndex) {
        //匹配完成
        if (index == s.length()) {
            return true;
        }
        //单词列表遍历完未找到匹配的单词
        if (dIndex == wordDict.size()) {
            return false;
        }
        //int wordDict.get(dIndex);
        if (back.containsKey(index)) {
            return back.get(index);
        }
        boolean res = false;
        String word = wordDict.get(dIndex);
        int length = word.length();
        //与下一个单词匹配
        if (length > s.length() - index) {
            res = dfs(s, wordDict, index, dIndex + 1);
        } else if (word.equals(s.substring(index, index + length))) {
            //与当前单词匹配有两种选择 1.直接与当前单词匹配，2.不与当前单词匹配与下一个单词匹配
            res = dfs(s, wordDict, index + length, 0) || dfs(s, wordDict, index, dIndex + 1);
        } else if (!word.equals(s.substring(index, index + length))) {
            //不匹配直接跳过与下一个匹配
            res = dfs(s, wordDict, index, dIndex + 1);
        }
        back.put(index, res);
        return res;
    }
}

[HCWGH]

单词拆分II,回溯思想

class Solution {
    // 记录结果
    List<String> res = new LinkedList<>();
    // 记录回溯算法的路径
    LinkedList<String> track = new LinkedList<>();
    List<String> wordDict;

    // 主函数
    public List<String> wordBreak(String s, List<String> wordDict) {
        this.wordDict = wordDict;
        // 执行回溯算法穷举所有可能的组合
        backtrack(s, 0);
        return res;
    }

    // 回溯算法框架
    void backtrack(String s, int i) {
        // base case
        if (i == s.length()) {
            // 找到一个合法组合拼出整个 s，转化成字符串
            res.add(String.join(" ", track));
            return;
        }

        // 回溯算法框架
        for (String word : wordDict) {
            // 看看哪个单词能够匹配 s[i..] 的前缀
            int len = word.length();
            if (i + len <= s.length()
                && s.substring(i, i + len).equals(word)) {
                // 找到一个单词匹配 s[i..i+len)
                // 做选择
                track.addLast(word);
                // 进入回溯树的下一层，继续匹配 s[i+len..]
                backtrack(s, i + len);
                // 撤销选择
                track.removeLast();
            }
        }
    }
}

[HCWGH]

单词拆分II,回溯思想

class Solution {
    List resList = new ArrayList<String>();

    public List<String> wordBreak(String s, List<String> wordDict) {
        backTrace(s, wordDict, new StringBuilder(), 0);
        return resList;
    }

    public void backTrace(String s, List<String> wordDict, StringBuilder builder, int index) {
        //base case
        if (index == s.length()) {
            resList.add(builder.deleteCharAt(builder.length() - 1).toString());
            return;
        }

        for (int i = 0; i < wordDict.size(); i++) {
            String word = wordDict.get(i);
            int length = word.length();
            //剪枝
            if (length > s.length() - index) {
                continue;
            }
            //剪枝
            if (!word.equals(s.substring(index, index + length))) {
                continue;
            }
            //回溯常规模板
            String newWord = word + " ";
            int builderLen = builder.length();
            builder.append(newWord);
            backTrace(s, wordDict, builder, index + length);
            builder.delete(builderLen, builder.length());
        }
    }

}

[wangyinwen]

回溯算法带上备忘录，时间复杂度是不是就和动态规划差不多了