140. Word Break II
給定一個字符串 s 和一個字符串字典 wordDict，在 s 中添加空格以構建一個句子，使得每個單詞都是有效的字典單詞。返回所有這樣的可能句子，順序不限。
注意：字典中的同一個單詞在分割中可以多次重用。
例如 1：
輸入：s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] 輸出：["cats and dog","cat sand dog"]
Python
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
word_set = set(wordDict)
memo = {}
def dfs(s):
if s in memo:
return memo[s]
res = []
if not s:
return [""]
for word in wordDict:
if s.startswith(word):
sublist = dfs(s[len(word):])
for sub in sublist:
res.append(word + ("" if not sub else " " + sub))
memo[s] = res
return res
return dfs(s)
16.57MB, 25ms
C++
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
unordered_map<string, vector<string>> memo;
return dfs(s, wordSet, memo);
}
private:
vector<string> dfs(const string& s, unordered_set<string>& wordSet,
unordered_map<string, vector<string>>& memo) {
if (memo.find(s) != memo.end()) {
return memo[s];
}
vector<string> res;
if (s.empty()) {
res.push_back("");
return res;
}
for (const string& word : wordSet) {
if (s.substr(0, word.size()) == word) {
vector<string> sublist = dfs(s.substr(word.size()), wordSet, memo);
for (const string& sub : sublist) {
res.push_back(word + (sub.empty() ? "" : " " + sub));
}
}
}
memo[s] = res;
return res;
}
};
9.46MB, 2ms
Javascript
/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function(s, wordDict) {
const wordSet = new Set(wordDict);
const memo = new Map();
const dfs = (s) => {
if (memo.has(s)) {
return memo.get(s);
}
const res = [];
if (s === '') {
res.push('');
return res;
}
for (const word of wordSet) {
if (s.startsWith(word)) {
const sublist = dfs(s.slice(word.length));
for (const sub of sublist) {
res.push(word + (sub ? ' ' + sub : ''));
}
}
}
memo.set(s, res);
return res;
};
return dfs(s);
};
48.69MB, 53ms
