Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.
Return all such possible sentences.
For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
这个问题可能由很多不同的组合结果，那么从第index个字母开始，一直到s的末尾，所有可能出现的单词组合用一个list存起来那么每一个index都对应一个list 所以很自然想到用map
public class Solution { private Map<Integer, List<String>> map = new HashMap<>(); public List<String> wordBreak(String s, List<String> wordDict) { return helper(s, 0, wordDict); } private List<String> helper(String s, int index, List<String> wordDict){ if(map.containsKey(index)){ return map.get(index); } List<String> list = new LinkedList<>(); if(index == s.length()){//如果当前的index超出s长度 list.add(""); } for(int i = index + 1; i <= s.length(); i++){ String tmp = s.substring(index, i); if(wordDict.contains(tmp)){//如果当前substring 是valid的 List<String> t = helper(s, i, wordDict);//寻找后半部分的list for(String str : t){ list.add(tmp + (str.equals("") ? "" : " " + str));组合成当前index的一个list } } } map.put(index, list); return list; } }
