word break II
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.
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: []
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
Map<String, List<String>> memo = new HashMap<>();
return dfs(s,wordSet,memo);
}
private List<String> dfs(String s,Set<String> wordSet,Map<String,List<String>> memo){
if(memo.containsKey(s)) return memo.get(s);
List<String > result = new ArrayList<>();
if(s.length() == 0){
result.add("");
return result;
}
for(int i = 1;i<=s.length();i++){
String prefix = s.substring(0,i);
if(wordSet.contains(prefix)){
String suffix = s.substring(i);
List<String> suffixBreaks = dfs(suffix,wordSet,memo);
for(String sentence : suffixBreaks){
if(sentence.isEmpty()){
result.add(prefix);
}else{
result.add(prefix+ " " + sentence);
}
}
}
}
memo.put(s,result);
return result;
}
}
L
Comments
Post a Comment