首页 > 代码库 > leetcode 140. Word Break II ----- java
leetcode 140. Word Break II ----- java
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"]
.
139题的延伸题,需要的出所有结果。
1、递归,仍旧超时。
public class Solution { String[] result; List list; public List<String> wordBreak(String s, Set<String> wordDict) { int len = s.length(),maxLen = 0; result = new String[len]; list = new ArrayList<String>(); for( String str : wordDict ){ maxLen = Math.max(maxLen,str.length()); } helper(s,0,wordDict,maxLen,0); return list; } public void helper(String s,int pos,Set<String> wordDict,int maxLen,int count){ if( pos == s.length() ){ String str = result[0]; for( int i = 1 ; i<count-1;i++){ str =str+ " "+result[i]; } if( count > 1) str = str+" "+result[count-1]; list.add(str); } int flag = 0; for( int i = pos;pos - i<maxLen && i<s.length();i++){ if( wordDict.contains( s.substring(pos,i+1) )){ result[count] = s.substring(pos,i+1); helper(s,i+1,wordDict,maxLen,count+1); flag = 1; } } } }
2、加入提前判断是否存在答案(即上一题的结论)就可以了。
public class Solution { String[] result; List list; public List<String> wordBreak(String s, Set<String> wordDict) { int len = s.length(),maxLen = 0; result = new String[len]; list = new ArrayList<String>(); for( String str : wordDict ){ maxLen = Math.max(maxLen,str.length()); } boolean[] dp = new boolean[len]; for( int i = 0 ;i<len;i++){ for( int j = i;j>=0 && i-j<maxLen;j-- ){ if( ( j == 0 || dp[j-1] == true ) && wordDict.contains(s.substring(j,i+1)) ){ dp[i] = true; break; } } } if( dp[len-1] == false) return list; helper(s,0,wordDict,maxLen,0); return list; } public void helper(String s,int pos,Set<String> wordDict,int maxLen,int count){ if( pos == s.length() ){ String str = result[0]; for( int i = 1 ; i<count-1;i++){ str =str+ " "+result[i]; } if( count > 1) str = str+" "+result[count-1]; list.add(str); } int flag = 0; for( int i = pos;pos - i<maxLen && i<s.length();i++){ if( wordDict.contains( s.substring(pos,i+1) )){ result[count] = s.substring(pos,i+1); helper(s,i+1,wordDict,maxLen,count+1); flag = 1; } } } }
leetcode 140. Word Break II ----- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。