Given a string s and a dictionary of strings wordDict,
add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Test Cases
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: []
Solution
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
return dfs(s, wordSet, new HashMap<String, List<String>>());
}
private List<String> dfs(String s, Set<String> wordDict, Map<String, List<String>> map) {
if (map.containsKey(s)) {
return map.get(s);
}
List<String> res = new ArrayList<String>();
if (s.length() == 0) {
res.add("");
return res;
}
for (String word : wordDict) {
int wlen = word.length();
if (s.length() < wlen) continue;
boolean match = true;
for(int i=0; i<wlen; i++) {
if (s.charAt(i) != word.charAt(i)) {
match = false;
break;
}
}
if (match) {
List<String>sublist = dfs(s.substring(word.length()), wordDict, map);
for (String sub : sublist)
res.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
map.put(s, res);
return res;
}
}class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
size = len(s)
memo = [None for _ in range(size + 1)]
def dfs(start):
if start > size - 1:
return [[]]
if memo[start]:
return memo[start]
res = []
for i in range(start, size):
word = s[start: i + 1]
if word in wordDict:
rest_res = dfs(i + 1)
for item in rest_res:
res.append([word] + item)
memo[start] = res
return res
res = dfs(0)
ans = []
for item in res:
ans.append(" ".join(item))
return ans