LeetCode 140. 单词拆分 II

https://leetcode-cn.com/problems/word-break-ii/

难度：困难

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

说明：

  • 分隔时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1：

输入:

s = "catsanddog"

wordDict = ["cat", "cats", "and", "sand", "dog"]

输出:

[
  "cats and dog",
  "cat sand dog"
]

示例 3：

输入:

s = "catsandog"

wordDict = ["cats", "dog", "sand", "and", "cat"]

输出:[]

解法1：回溯 + 记忆数组，记录当前字符串

  拆分单词，我们可以使用回溯法，遍历所有可能的组合。

  对于一个字符串 strs，遍历词典 wordDict 中的所有单词 word，判断这个字符串 strs 是否是以 word 开头，若是，则保存当前单词，并将 strs 中开头的 word 给截去，递归获取单词组合，当 strs 为空时，我们就找到了一个组合。

  如 catsanddog，先找到 cat ，截去后剩余 sanddog ，再找到 sand ，最后剩余 dog。

JS 代码：

var wordBreak = function(s, wordDict) {
    let res = [];
    let str = [];
    let len = wordDict.length;

    const helper = (strs) => {
        if (strs.length === 0) {
            res.push(str.slice().join(' '));
        }

        let size = strs.length;
        for (let i = 0; i < len; i++) {
            let word = wordDict[i];
            if (strs.startsWith(word)) {
                str.push(word);
                helper(strs.substring(word.length, size));
                str.pop();
            }
        }
    };

    helper(s);

    return res;
};

  不过未优化的回溯相当于是暴力解法，效率很低，会在 31 / 36 的用例处超时。

  因此需要使用记忆数组 memo 来优化，说是数组，这边其实是一个 map。

  根据我们前面回溯法的思路，每次在递归函数中，我们是对一个字符串 strs 来判断这个字符串是否能被拆分为字典中的单词，这样，若当前字符串 strs 已经递归判断了一次，发现无法被拆分，那么我们下次再遇到这个字符串 strs 时，我们就能直接返回，而不用再继续对其回溯判断是否能被拆分。

  因此对于每个遍历的字符串 strs ，若其在 memo 中的记录为 false ，那么就可以直接返回，节省了剩余的判断时间。

JS 代码：

var wordBreak = function(s, wordDict) {
    let res = [];
    let str = [];
    let memo = new Map();
    let wordMap = new Set(wordDict);

    const helper = (strs) => {
        // 若 strs 已被判断过是无法拆分的，那么直接返回 false
        if (memo.get(strs) === false) {
            return false;
        }
		
        // 若 strs 为空，表示我们的单词拆分成功，记录拆分结果且返回 true
        if (strs.length === 0) {
            res.push(str.slice().join(' '));
            return true;
        }

        let size = strs.length;
        let flag = false;
        for (let i = 0; i <= wordDict.length; i++) {
            let word = wordDict[i];
            if (strs.startsWith(word)) {
                str.push(word);
                // 所有组合情况中，只要有一个能够正确拆分，memo 中的记录就为 true
                flag = helper(strs.substring(word.length, size)) || flag;
                str.pop();
            }
        }
        memo.set(strs, flag);

        return flag;
    };
    
    helper(s);

    return res;
};

解法2：回溯 + 记忆数组，记录索引 i 到字符结尾的字符串能拆分的组合

  该思路来自官方解答 。

  假设初始字符串为 pineapplepenapple ，我们已经拆分了一个 pine ，当前字符索引为 4 即 a ，那么从索引 4 到字符串结尾的子串能拆分的组合为 apple pen apple 和 applepen apple，此时只要再加上一个 pine ，即能获取以单词 pine 开头的所有组合：pine apple pen apple 和 pine applepen apple 。

  memo 保存索引对应的所有组合，memo[4] 中保存的就是 apple pen apple、applepen apple，当第二次递归遍历到这个索引，那么直接返回这个组合就好了。

  这边的字符拆分策略和上一个解法稍有不同，上一个解法中是遍历 wordDict 中的所有字符来判断字符是否在字符串中，这边是遍历整个字符串 strs，从当前索引start 开始先截取一个字符，再截取两个字符…来判断这个字符是否在 wordDict 中出现，若出现，则可以把当前字符与获取的所有拆分单词组合在一起。

JS 代码：

var wordBreak = function(s, wordDict) {
    let map = new Set(wordDict);
    let len = s.length;
    let res = [];
    let memo = new Map();

    const getBreakWord = (start) => {
        // 若前面已得到过已 start 开头到结尾的单词拆分组合，那么直接返回
        if (memo.has(start)) {
            return memo.get(start);
        }

        let words = [];
        // 若当前索引位置为字符串结尾，那么表示能正确拆分单词，因此往组合中加入一个空数组，供与最后一个单词组合
        if (start === len) {
            words.push([]);
        }

        for (let i = start + 1; i <= len; i++) {
            let word = s.substring(start, i); // 获取子串
            if (map.has(word)) {
                let nextWords = getBreakWord(i);
                // 将当前单词与所有拆分单词组合在一起
                for (let nextWord of nextWords) {
                    words.push([word, ...nextWord]);
                }
            }
        }
        memo.set(start, words);

        return words;
    };

    let wordBreaks = getBreakWord(0);

    for (let arr of wordBreaks) {
        res.push(arr.join(' '));
    }

    return res;
};

 目录