首页 > 代码库 > 140. Word Break II
140. Word Break II
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.
通过hashMap进行记忆化搜索, 不过是从单词表中走, 而非s的长度上遍历
public List<String> wordBreak(String s, List<String> wordDict) { List<String> res = new LinkedList<String>(); if (wordDict.size() == 0 || wordDict == null) { return res; } return helper(new HashMap<String, LinkedList<String>>(), s, wordDict); } private LinkedList helper( HashMap<String, LinkedList<String>> map, String s, List<String> wordDict) { if (map.containsKey(s)) { return map.get(s); } LinkedList<String> list = new LinkedList<>(); if (s.length() == 0) { list.add(""); return list; } for (String word : wordDict) { if (s.startsWith(word)) { String sub = s.substring(word.length()); LinkedList<String> subList = helper(map, sub, wordDict); for (String item : subList) { list.add(word + (item.isEmpty() ? "" : " ") + item); } } } map.put(s, list); return list; }
140. Word Break II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。