I140过了，发50个包子# pets - 心有所宠
s*u
1 楼
之前有人放过这个题，就是提供一个bool isWord(string s)的函数，要求得到一个
string拆成若干个word的所有组合，word之间用空格隔开。
自己写了下，用递归 + memoization，想问问这个题有iteration的做法么？如果是每
个string有唯一解（只有一种拆法）呢？
vector wordBreak( string str, map >& cache){
vector vs;
if( str.empty() ){
vs.push_back(str);
return vs;
}
if(cache.count(str) > 0)
return cache[str];
string prefix;
string suffix;
vector segSuffix;
for( int len = 1;len <= str.size(); len++){
prefix = str.substr(0,len);
if( isWord(prefix)){
suffix = str.substr(len);
segSuffix = wordBreak( suffix,cache );
for( int i = 0; i < segSuffix.size(); i++ ){
vs.push_back( prefix + ' ' + vs[i]);
}
}
}
cache[str] = vs;
return vs;
}
string拆成若干个word的所有组合，word之间用空格隔开。
自己写了下，用递归 + memoization，想问问这个题有iteration的做法么？如果是每
个string有唯一解（只有一种拆法）呢？
vector
vector
if( str.empty() ){
vs.push_back(str);
return vs;
}
if(cache.count(str) > 0)
return cache[str];
string prefix;
string suffix;
vector
for( int len = 1;len <= str.size(); len++){
prefix = str.substr(0,len);
if( isWord(prefix)){
suffix = str.substr(len);
segSuffix = wordBreak( suffix,cache );
for( int i = 0; i < segSuffix.size(); i++ ){
vs.push_back( prefix + ' ' + vs[i]);
}
}
}
cache[str] = vs;
return vs;
}
