给定一个字符串 String s =
"leetcode"
dict =
["leet", "code"]
查看一下是够是字典中的词语组成。假设是返回true，否则返回false。
下边提供3种思路
1.动态算法
import java.util.HashSet;
import java.util.Set; public class WordBreak1 {
public static void main(String[] args) {
//"["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
//String s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab";
String s ="LeetCodea";
Set<String> dict = new HashSet<String>();
dict.add("Leet");
dict.add("Code");
dict.add("a");
System.out.println(wordBreak(s,dict));
}
public static boolean wordBreak(String s, Set<String> dict) {
boolean[] t = new boolean[s.length() + 1];
t[0] = true; // set first to be true, why?
// Because we need initial state for (int i = 0; i < s.length(); i++) {
// should continue from match position
if (!t[i])
continue;
for (String a : dict) {
int len = a.length();
int end = i + len;
if (end > s.length())
continue; if (t[end])
continue; if (s.substring(i, end).equals(a)) {
t[end] = true;
}
}
}
return t[s.length()];
}
}
2.普通算法(1)
import java.util.Set;
public class WorkBreak2 {
public boolean wordBreak(String s, Set<String> dict) {
return wordBreakHelper(s, dict, 0);
}
public boolean wordBreakHelper(String s, Set<String> dict, int start) {
if (start == s.length())
return true;
for (String a : dict) {
int len = a.length();
int end = start + len;
// end index should be <= string length
if (end > s.length())
continue;
if (s.substring(start, start + len).equals(a))
if (wordBreakHelper(s, dict, start + len))
return true;
}
return false;
}
}3.普通算法(2)
import java.util.Set;
public class WordBreak3 {
public static boolean wordBreak(String s, Set<String> dict) {
// input validation
// Base case
if (dict.contains(s))
return true;
else {
for (int i = 0; i < s.length(); i++) {
String sstr = s.substring(0, i);
if (dict.contains(sstr))
return wordBreak(s.substring(i), dict);
}
}
return false;
}
}可是以上的算法有一个问题，就是遇到这样的情况。INPUT: "programcreek", ["programcree","program","creek"]. 无能为力。
大家讨论下吧？