首页 > 代码库 > [leetcode] Word Break2
[leetcode] Word Break2
题目：(DP, Backtracing)
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
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"].
题解：
一条经典的 DP+Backtracing的题。dp 部分就是word break的代码， 然后后面一段就是backtracing的代码。
public class Solution { public boolean wordBreakcheck(String s, Set<String> dict) { if(s==null || s.length()==0) return true; boolean[] res = new boolean[s.length()+1]; res[0] = true; for(int i=0;i<s.length();i++){ StringBuilder str = new StringBuilder(s.substring(0,i+1)); for(int j=0;j<=i;j++){ if(res[j] && dict.contains(str.toString())){ res[i+1] = true; break; } str.deleteCharAt(0); } } return res[s.length()]; } public ArrayList<String> wordBreak(String s, Set<String> dict) { ArrayList<String> res = new ArrayList<String>(); if(s==null || s.length()==0) return res; if(wordBreakcheck(s,dict)) helper(s,dict,0,"",res); return res; } private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res){ if(start==s.length()){ res.add(item); return; } StringBuilder str = new StringBuilder(); for(int i=start;i<s.length();i++){ str.append(s.charAt(i)); if(dict.contains(str.toString())){ String newItem = new String(); if(item.length()>0) newItem = item + " " + str.toString(); else newItem = str.toString(); helper(s,dict,i+1,newItem,res); } } }}
[leetcode] Word Break2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。