发布于 2016-01-12 10:38:23 | 274 次阅读 | 评论: 0 | 来源: PHPERZ
Leetcode 在线编程网站
leetcode 是一个美国的在线编程网站，上面主要收集了各大IT公司的笔试面试题，对于应届毕业生找工作是一个不可多得的好帮手。
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s ="leetcode",
dict =["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
典型的DP题，dp[i]表示前i个字符是否可分解成单词，那么
dp[i] = dp[j] && dict.contains(s.substring(j, i)) (j = 0, 1, ..., i-1, 只要任意一个满足即可);
这道题不推荐用DFS，时间复杂度会很高，worst case达到O(2^n)。
这道题的Follow up,比如返回所有组合，或者只返回一个解，前者即是LeetCode原题Word Break II, 具体见下文。
time: O(n^2), space: O(n)
public class Solution {
public boolean wordBreak(String s, Set<String> dict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for(int i = 1; i <= len; i++) {
for(int j = 0; j < i; j++) {
if(dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}
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，时间复杂度较低，但是比较耗内存，意味着对于每个Index, 我们可能都要存其对应所有解。另一种是DFS，空间复杂度较低，但是时间时间复杂度较高，我们可以采用memorization优化时间复杂度。
注意DP方法种为了过OJ上一个edge case, 用Word Break的解法先检测整个字符串是否能够分解，不能的话就没有必要继续算了。
DP: time: O(n^2*k), space: O(nk), 假设k表示平均每个长度对应解的个数
DFS: time: O(2^n), space: O(n)
public class Solution {
public List<String> wordBreak(String s, Set<String> wordDict) {
// 判断是否能够分解
if (!helper(s, wordDict)) {
return new ArrayList<String>();
}
// 记录字符串s.substring(0, i)对应的解
HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>();
map.put(0, new ArrayList<>());
map.get(0).add("");
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (map.containsKey(j) && wordDict.contains(s.substring(j, i))) {
if (!map.containsKey(i))
map.put(i, new ArrayList<>());
for (String str : map.get(j)) {
map.get(i).add(str + (str.equals("") ? "" : " ") + s.substring(j, i));
}
}
}
}
return map.get(s.length());
}
private boolean helper(String s, Set<String> wordDict) {
boolean dp[] = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
}
}
}
return dp[s.length()];
}
}
public class Solution {
public List<String> wordBreak(String s, Set<String> wordDict) {
List<String> res = new ArrayList<String>();
// 用来记录s.substring(i)这个字符串能否分解
boolean[] possible = new boolean[s.length() + 1];
Arrays.fill(possible, true);
dfs(res, "", s, wordDict, 0, possible);
return res;
}
public static void dfs(List<String> res, String cur, String s, Set<String> wordDict, int start, boolean[] possible) {
if (start == s.length()) {
res.add(cur);
return;
}
for (int i = start + 1; i <= s.length(); i++) {
String str = s.substring(start, i);
if (wordDict.contains(str) && possible[i]) {
int prevSize = res.size();
dfs(res, cur + (cur.equals("") ? "" : " ") + str, s, wordDict, i, possible);
// DFS后面部分结果没有变化，说明后面是没有解的
if (res.size() == prevSize)
possible[i] = false;
}
}
}
}