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”].
UPDATE (2017/1/4): The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.
public class Solution { HashMap<String, List<String>> map = new HashMap<String, List<String>>(); public List<String> wordBreak(String s, List<String> wordDict) { if(map.containsKey(s)) return map.get(s); List<String> res = new ArrayList<String>(); if(wordDict.contains(s)) res.add(s); for (int i = 1; i < s.length(); i++) { String left = s.substring(0, i); String right = s.substring(i); if(wordDict.contains(left) && contain(right, wordDict)) { List<String> tmp = wordBreak(right, wordDict); for (String str : tmp) res.add(left + " " + str); } } map.put(s, res); return res; } public boolean contain(String right, List<String> wordDict) { for (int i = 0; i < right.length(); i++) { if(wordDict.contains(right.substring(i))) return true; } return false; }}新闻热点
疑难解答
