给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
样例
s = "lintcode"
dict = ["lint","code"]
返回 true 因为"lintcode"可以被空格切分成"lint code"
解题
DFS
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;
// write your code here
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
Main m = new Main();
while(in.hasNext()){
String s = in.nextLine();
String[] str = in.nextLine().split(" ");
Set<String> dict = new TreeSet<String>();
for(int i = 0;i<str.length;i++)
dict.add(str[i]);
int start = 0;
boolean flag = m.wordBreak(s, dict, start);
System.out.println(flag);
}
}
public boolean wordBreak(String s,Set<String> dict,int start){
if((s==null ||s.length() ==0) && (dict == null || dict.size()==0))
return true;
Iterator it = dict.iterator();
if(start == s.length())
return true;
while(it.hasNext()){
String t = (String)it.next();
int end = start + t.length();
if(end > s.length())
continue;
if(s.substring(start,end).equals( t )){
if(wordBreak(s,dict,end)){
return true;
}
}
}
return false;
}
}
95%数据运行超时
动态规划求解
定义数组dp dp[i] =true表示 字符串 s 子串0 - (i-1)在字典中存在
当dp[s.length()] == true 时候表示可以由字典内的单词组成s
至于为什么？
自己根据输出发现：当有一个字符没有出现，后面的将都会为false，一次没有找到，破坏了后面的继续查找字符串的长度，后面就再也找不到，最后一个位置为false
自己测试
public static void main(String[] args){
Solution s = new Solution();
Set<String> dict = new HashSet<String>();
String str = "123";
dict.add("1");
dict.add("2");
dict.add("64");
System.out.println(s.wordBreak(str, dict));
dict.add("3");
System.out.println(s.wordBreak(str, dict));
}输出
[true, false, false, false]
[true, true, false, false]
[true, true, true, false]
[true, true, true, false]
false
[true, false, false, false]
[true, true, false, false]
[true, true, true, false]
[true, true, true, true]
true
public class Solution {
/**
* @param s: A string s
* @param dict: A dictionary of words dict
*/
public boolean wordBreak(String s, Set<String> dict) {
// write your code here
if((s==null ||s.length() ==0) && (dict == null || dict.size()==0))
return true;
return wordBreak(s,dict,0);
}
public boolean wordBreak(String s,Set<String> dict,int start){
boolean dp[] = new boolean[s.length() + 1];
dp[0] = true;//初始值
for(int i = 0;i<s.length();i++){
if(!dp[i])
continue;
for(String t:dict){
int len = t.length();
int end = i+ len;
if(end > s.length())
continue;
if(s.substring(i,end).equals(t)){
dp[end] = true;
}
}
}
return dp[s.length()];
}
}