j*********6
发帖数: 407 | 1 求高人指点 有什么好办法？
用了memorized 但还是不行~
Time Limit Exceeded
Last executed input: "
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
, ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","
aaaaaaaaaa"] | p*****2
发帖数: 21240 | | j*********6
发帖数: 407 | 3 求二爷 进一步赐教~ 其实对剪枝的概念理解的不是很到位 | p*****2
发帖数: 21240 | 4
就是循环的时候在肯定不可能有结果的时候就提前return。比如字典word的长度最大是
5，那你循环到5就不用继续下去了。当然这题我也没做。不知道剪枝能不能过，你可以
试试。
【在 j*********6 的大作中提到】
: 求二爷 进一步赐教~ 其实对剪枝的概念理解的不是很到位
| j*********6
发帖数: 407 | 5 一语点破 多谢二爷
mark一下 第一次与二爷的正面交流！！ | p*****2
发帖数: 21240 | 6 我也练了一下
(def dict #{"cat", "cats", "and", "sand", "dog"})
(defn- dfs [s start list]
(if (= start (count s))
(println (reverse list))
(doseq [i (range start (count s))]
(let [word (subs s start (inc i))]
(when (contains? dict word)
(dfs s (inc i) (cons word list)))))))
(defn wordBreak [s] (dfs s 0 '()))
(wordBreak "catsanddog") | g***j
发帖数: 1275 | 7 Last executed input: "
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
, ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","
aaaaaaaaaa"]
这个可以过么？
我总是超时
【在 p*****2 的大作中提到】
: 我也练了一下
: (def dict #{"cat", "cats", "and", "sand", "dog"})
: (defn- dfs [s start list]
: (if (= start (count s))
: (println (reverse list))
: (doseq [i (range start (count s))]
: (let [word (subs s start (inc i))]
: (when (contains? dict word)
: (dfs s (inc i) (cons word list)))))))
: (defn wordBreak [s] (dfs s 0 '()))
| d*****v
发帖数: 72 | 8 用了二爷的方法还是过不去，最后还是得用dp来做，然后回溯建立字符串 | p*****2
发帖数: 21240 | 9
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
,"
试了一下，过不了。主要是练练clojure。
【在 g***j 的大作中提到】
: Last executed input: "
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
: , ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","
: aaaaaaaaaa"]
: 这个可以过么？
: 我总是超时
| t**********r
发帖数: 2153 | 10 加一个对alpha coverage的测试就可以了.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
,"
【在 j*********6 的大作中提到】
: 求高人指点 有什么好办法？
: 用了memorized 但还是不行~
: Time Limit Exceeded
: Last executed input: "
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
: , ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","
: aaaaaaaaaa"]
| | | J****3
发帖数: 427 | | j*********6
发帖数: 407 | 12 我是用DFS，和memorized 再加上 二爷指导的 pruning, 代码如下 不够感觉写得有些
麻烦 有什么问题请大家慷慨指出
顺便求教这种问题怎么分析时间复杂度
public class Solution {
public ArrayList wordBreak(String s, Set dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
// 1. get the min and max length of words in dictionary, used for
pruning.
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for(String str : dict){
min = Math.min(min, str.length());
max = Math.max(max, str.length());
}
Map> memorized = new HashMap
ArrayList>();
return wordBreak1(s, dict, min, max, memorized);
}
private ArrayList wordBreak1(String s, Set dict,
int min, int max, Map> memorized){
if(memorized.containsKey(s)){
return memorized.get(s);
}
ArrayList res = new ArrayList();
if(s == null || s.length() == 0){
return res;
}
if(dict.contains(s)){
res.add(s);
}
for(int i = min - 1; i < Math.min(s.length(), max); i++){
String prefix = s.substring(0, i + 1);
if(dict.contains(prefix)){
String suffix = s.substring(i + 1);
List suffixBreak = wordBreak1(suffix, dict, min, max
, memorized);
if(!suffixBreak.isEmpty()){
for(String str : suffixBreak){
res.add(prefix + " " + str);
}
}
}
}
memorized.put(s, res);
return res;
}
} | a*****a
发帖数: 46 | 13 光用DP还不行，必须得等结束后回溯找所有路径才过了测试。。。
我在DP里存的是可能路径的所有节点（也可以只存上一个节点，但是那样回溯不好写）
，这样的话和仅DP的区别在于每次拷贝的只是节点，省掉的时间就是拷贝生成字符串的
时间。
呵呵，这测试真严格啊。C++的有没有可能不回溯也能过测试？
贴出code来，欢迎各位牛人指正~
private ArrayList getPath(String s, int n, ArrayList
Integer>> pres) {
ArrayList res = new ArrayList();
for (int pre : pres.get(n-1)) {
if (pre == 0) {
res.add(s.substring(0, n));
} else {
ArrayList preres = getPath(s, pre, pres);
String sub = s.substring(pre, n);
for (String ss : preres) { // 拷贝前面的节点
res.add(ss + " " + sub);
}
}
}
return res;
}
private ArrayList wordBreakDP2(String s, Set dict) {
int n = s.length();
ArrayList> pres = new ArrayList
>>(n);
// initialize
for (int i=0; i
pres.add(new ArrayList());
}
// DP
for (int i=0; i
for (int j=0; j<=i; ++j) {
String ss = s.substring(j, i+1);
if ((j==0 || pres.get(j-1).size()>0) && dict.contains(ss)) {
pres.get(i).add(j);
}
}
}
return getPath(s, n, pres);
} | a*****a
发帖数: 46 | 14 求详解~
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
【在 t**********r 的大作中提到】
: 加一个对alpha coverage的测试就可以了.
:
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
: ,"
| l*n
发帖数: 529 | 15 clojure写好了在服务器端能运行？不需要特别的环境么？
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
【在 p*****2 的大作中提到】
:
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
: ,"
: 试了一下，过不了。主要是练练clojure。
| m**********g
发帖数: 153 | 16 先dp, 然后dfs, 用dp信息剪枝.
class Solution {
void getSentence(string &s, int start, string sentence, vector &
output, unordered_set &dict, bool *breakable)
{
if(start == s.size()) {
sentence.erase(sentence.end() -1);
output.push_back(sentence);
return;
}
for(int i=start; i
if(breakable[i+1] == false) //prune here
continue;
string tmp=s.substr(start, i-start+1);
if(dict.find(tmp) != dict.end()) {
getSentence(s, i+1, sentence+tmp+" ", output, dict,
breakable);
}
}
}
public:
vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector output;
string sentence;
bool breakable[s.size()+1];
//mark each index point as true or false.
breakable[s.size()] = true;
for(int i=s.size()-1; i>=0; i--){
int j;
for(j=i; j
string tmp = s.substr(i, j-i+1);
if(dict.find(tmp) != dict.end() && breakable[j+1]) {
breakable[i] = true; //valid sentence from i to end.
break;
}
}
if(j == s.size())
breakable[i] = false;
}
getSentence(s, 0, sentence, output, dict, breakable);
return output;
}
}; | p*****2
发帖数: 21240 | 17
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
你指的是什么环境呀？web server还是什么？
【在 l*n 的大作中提到】
: clojure写好了在服务器端能运行？不需要特别的环境么？
:
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
| g***1
发帖数: 8 | | p*********y
发帖数: 17 | 19 优化一下就能过。
==================================================
public class Solution {
public ArrayList wordBreak(String s, Set dict) {
int N = s.length();
ArrayList result = new ArrayList();
if (N == 0) return result;
int maxLen = 0;
for (String str : dict) {
maxLen = Math.max(maxLen, str.length());
}
StringBuilder buffer = new StringBuilder();
HashSet invalid = new HashSet();
wordBreak(s, dict, 0, buffer, result, maxLen, invalid);
return result;
}
private boolean wordBreak(String s, Set dict, int n,
StringBuilder buffer, ArrayList result,
int maxLen, HashSet invalid) {
int N = s.length();
if (n == N) {
String sentence = buffer.toString();
result.add(sentence.substring(0, sentence.length()-1));
return true;
}
int i = n;
if (invalid.contains(n)) {
return false;
}
boolean hasCombination = false;
while (i < N && i-n+1 <= maxLen) {
String str = s.substring(n, i+1);
if (dict.contains(str)) {
int oldLen = buffer.length();
buffer.append(str+' ');
boolean flag = wordBreak(s, dict, i+1, buffer, result,
maxLen, invalid);
buffer.delete(oldLen, buffer.length());
if (flag) hasCombination = true;
}
i++;
}
if (!hasCombination) invalid.add(n);
return hasCombination;
}
} | g*********e
发帖数: 14401 | 20 你可以用一个hash记录每个substring的结果 然后dp 。 别担心 oj似乎对空间使用很
宽容。
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
,"
【在 j*********6 的大作中提到】
: 求高人指点 有什么好办法？
: 用了memorized 但还是不行~
: Time Limit Exceeded
: Last executed input: "
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
: , ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","
: aaaaaaaaaa"]
| | | s********u
发帖数: 1109 | 21 我现在对这类题目是这么思考的：
1.问题的起点（字符串首）和终点（字符串尾）都是“收敛”的，因此可以考虑用dp。
2.用dp的话，就是从起点开始（终点其实也行，因为空字符串的解都是true，都已知）
，根据1~n-1个节点的情况，推断n的情况。因为需要记录path，又不是backtracking，
所以用prev数组（每个节点的前驱节点）来记录。
3.可能有多条path，所以prev是一个vector >。记录完毕之后需要从终点
出发，回溯遍历这些路径，直到prev取出来的index是-1。 | s********u
发帖数: 1109 | 22 写了一下，觉得难点主要在回溯写这个path，如果维护不好，很容易出bug。
52ms通过。
class Solution {
public:
void backtracking( int end,const vector >&prev,const string
&s, vector &paths, string &path ){
if(end == -1){
paths.push_back(path);
return;
}
int prev_end;
string word;
const string local = path;
for(int i = 0; i < prev[end].size(); i++){
prev_end = prev[end][i];
word = s.substr( prev_end+1, end - prev_end );
if( !path.empty())
path = word + " " + path;
else
path = word;
backtracking(prev_end, prev, s, paths, path);
path = local;
}
}
vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int prev_end = -1, end = 0;
int size = s.size();
vector > prev(size);
bool *success = new bool[size + 1];
success[0] = true;
for( end = 0; end < size; end++){
for( prev_end = -1; prev_end < end; prev_end++){
if(success[prev_end + 1] && dict.find(s.substr( prev_end+1,
end-prev_end) ) != dict.end() ){
success[end+1] = true;
prev[end].push_back(prev_end);
}
}
}
vector paths;
string path;
if(!success[size])
return paths;
backtracking( size - 1,prev,s, paths, path );
return paths;
}
}; | s********u
发帖数: 1109 | 23 这个写法，好像就是只存上一个节点吧。如果存路径上的所有节点，岂不是要三维数组
？路径是一层vector，多条路径就是2层vector，然后以每个节点为终点，就是3层
vector。。。。
【在 a*****a 的大作中提到】
: 光用DP还不行，必须得等结束后回溯找所有路径才过了测试。。。
: 我在DP里存的是可能路径的所有节点（也可以只存上一个节点，但是那样回溯不好写）
: ，这样的话和仅DP的区别在于每次拷贝的只是节点，省掉的时间就是拷贝生成字符串的
: 时间。
: 呵呵，这测试真严格啊。C++的有没有可能不回溯也能过测试？
: 贴出code来，欢迎各位牛人指正~
: private ArrayList getPath(String s, int n, ArrayList: Integer>> pres) {
: ArrayList res = new ArrayList();
: for (int pre : pres.get(n-1)) {
| s*****n
发帖数: 994 | 24 dp + backtracking。 之前用了hashtable能过break word I，但是过不了II，可能是
string constructor太耗时了吧
class Solution {
public:
void backTracking (const string& s, vector >&prev, int index
, vector& output){
for (int i=0; i
int prev_index = prev[index][i];
vector prev_output(0);
if (prev_index != 0)
backTracking (s, prev, prev_index, prev_output);
else
prev_output = vector (1, "");
for (int j=0; j
if (prev_index != 0)
output.push_back(prev_output[j]+" "+s.substr(prev_index,index-
prev_index));
else
output.push_back(s.substr(prev_index,index-prev_index));
}
}
}
vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int n = s.size();
if (n == 0) return vector (0);
vector > dp_prev(n+1, vector (0));//dp_prev[k] has
all the prev nodes for substr(0,k-1)
dp_prev[0] = vector (1,-1);//assign any number to it make it
valid
for (int i=1; i
for (int j=0; j
if (dp_prev[j].size()>0 && dict.find(s.substr(j,i-j))!=dict.end()){
dp_prev[i].push_back(j);
}
}
}
//backtracking
vector output(0);
backTracking (s, dp_prev, n, output);
return output;
}
}; | w**2
发帖数: 29 | 25 其实可以用 HashMap 保存从某个index出发到终点的DFS的所有可能路径。
代码写得糙 请包涵：
public class Solution {
public ArrayList wordBreak(String s, Set dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
ArrayList rl = new ArrayList();
if (s==null) return rl;
HashMap> hm = new HashMap
ArrayList>();
return reach(s,0,s.length()-1,dict,hm);
}
public ArrayList reach(String s, int start, int end, Set
dict, HashMap> hm){
ArrayList rl = new ArrayList();
if (hm.containsKey(start))
return hm.get(start);
if (start>end){
rl.add("");
return rl;
}
for (int i=start;i<=end;i++)
if (dict.contains(s.substring(start,i+1))){
ArrayList rest = reach(s,i+1,end,dict,hm);
if (rest.size()>0)
for(String t : rest)
if (t.equals("")){
rl.add(s.substring(start,i+1));
}else{
rl.add(s.substring(start,i+1)+" "+t);
}
}
hm.put(start,rl);
return rl;
}
}
【在 p*****2 的大作中提到】
:
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
: 你指的是什么环境呀？web server还是什么？
|
|
