Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
題意：給定一個(gè)字符串和一個(gè)字符串?dāng)?shù)組，問(wèn)這個(gè)字符串能否正好被這個(gè)數(shù)組里的word分割火本。
思路：
第一個(gè)思路想到的是深度優(yōu)先搜索危队，從頭開(kāi)始尋找每種可能的分割方案聪建，直到找到一個(gè)正好分割的方案，返回true茫陆。
public boolean wordBreak(String s, List<String> wordDict) {
if (s == null || s.length() == 0) {
return true;
}
HashSet<String> set = new HashSet<>();
for (String word : wordDict) {
set.add(word);
}
return dfs(s, 0, set);
}
private boolean dfs(String s, int start, HashSet<String> set) {
if (start == s.length()) {
return true;
}
for (int i = start + 1; i <= s.length(); i++) {
String str = s.substring(start, i);
if (!set.contains(str)) {
continue;
}
if (dfs(s, i, set)) {
return true;
}
}
return false;
}
提交后金麸，leetcode提示超時(shí)，看到relate topic提示是動(dòng)態(tài)規(guī)劃方法簿盅。
于是從這個(gè)角度想到了這個(gè)解法谤专，dp[k]表示從頭開(kāi)始到第k個(gè)字符的字符串能否被dict完美break，dp[0]默認(rèn)為true粥烁，可理解為空字符串能夠被break拄丰。
求解dp[k]是否為true，只需要看0<=i<k這個(gè)范圍是否存在某處使得dp[i] == true并且s.substring(i, k)在dict中讨盒。
從dp[1]開(kāi)始迭代求出dp[s.length()]解取，最后就看dp[s.length()]是否為true。
public boolean wordBreak1(String s, List<String> wordDict) {
if (s == null || s.length() == 0) {
return true;
}
HashSet<String> set = new HashSet<>();
for (String word : wordDict) {
set.add(word);
}
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int end = 1; end <= s.length(); end++) {
for (int start = 0; start < end; start++) {
if (dp[start] && set.contains(s.substring(start, end))) {
dp[end] = true;
break;
}
}
}
return dp[s.length()];
}