140. Word Break II

[Tcdian]

140. Word Break II

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

Note

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

Example 1

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Example 2

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

[Tcdian]

Solution

• JavaScript Solution

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function(s, wordDict) {
    const direction = new Set();
    for (let i = 0; i < wordDict.length; i++) {
        direction.add(wordDict[i]);
    }
    const cache = new Map();

    return _wordBreak(s);

    function _wordBreak(s) {
        if (cache.has(s)) {
            return cache.get(s);
        }
        const result = direction.has(s) ? [s] : [];
        for (let i = 0; i < s.length; i++) {
            const word = s.slice(i);
            if (direction.has(word)) {
                const others = _wordBreak(s.slice(0, i));
                for (let j = 0; j < others.length; j++) {
                    result.push (`${others[j]} ${word}`);
                }
            }
        }
        cache.set(s, result);
        return result;
    }
};

• TypeScript Solution

function wordBreak(s: string, wordDict: string[]): string[] {
    const direction: Set<string> = new Set();
    for (let i = 0; i < wordDict.length; i++) {
        direction.add(wordDict[i]);
    }
    const cache: Map<string, string[]> = new Map();

    return _wordBreak(s);

    function _wordBreak(s: string): string[] {
        if (cache.has(s)) {
            return cache.get(s) as string[];
        }
        const result: string[] = direction.has(s) ? [s] : [];
        for (let i = 0; i < s.length; i++) {
            const word = s.slice(i);
            if (direction.has(word)) {
                const others = _wordBreak(s.slice(0, i));
                for (let j = 0; j < others.length; j++) {
                    result.push(`${others[j]} ${word}`);
                }
            }
        }
        cache.set(s, result);
        return result;
    }
};