B********t
发帖数: 147 | 1 题目：找dict中最长的单词，这个单词必须由dict里的单词组成。
bool myfunc(string s1, string s2)
{
return (s1.size() > s2.size());
}
bool findLongestWord_helper(string &s, map &hm)
{
for(int i = 1; i <= s.size(); i++)
{
string sub_f(s, 0, i);
if(hm[sub_f])
{
if(i == s.size())
return true;
string sub_b(s, i, s.size()-i);
if(findLongestWord_helper(sub_b, hm))
return true;
}
}
return false;
}
string findLongestWord(vector &vs)
{
string result("");
sort(vs.begin(), vs.end(), myfunc);
map hashmap;
for(int i = 0; i < vs.size(); i++)
hashmap[vs[i]] = true;
for(int i = 0; i < vs.size(); i++)
{
hashmap[vs[i]] = false;//加上这句就好了
if(findLongestWord_helper(vs[i], hashmap))
{
result = vs[i];
break;
}
}
return result;
} | c********t
发帖数: 5706 | 2 为什么这么复杂？还要用hashmap? 直接扫一遍不行吗？
【在 B********t 的大作中提到】
: 题目：找dict中最长的单词，这个单词必须由dict里的单词组成。
: bool myfunc(string s1, string s2)
: {
: return (s1.size() > s2.size());
: }
: bool findLongestWord_helper(string &s, map &hm)
: {
: for(int i = 1; i <= s.size(); i++)
: {
: string sub_f(s, 0, i);
| e****e
发帖数: 418 | | d*********g
发帖数: 154 | 4 for(int i = 0; i < vs.size(); i++)
{
if(findLongestWord_helper(vs[i], hashmap))
{
result = vs[i];
break;
}
}
为什么这里break了？不是要找最长的么？你这里只是找到一个由dict里面的单词构成
的单词之后就break了吧？ | B********t
发帖数: 147 | 5 求问一遍怎么扫
【在 c********t 的大作中提到】
: 为什么这么复杂？还要用hashmap? 直接扫一遍不行吗？
| B********t
发帖数: 147 | 6 我把dict sort了的 从最长的开始找 找到就可以退出了
【在 d*********g 的大作中提到】
: for(int i = 0; i < vs.size(); i++)
: {
: if(findLongestWord_helper(vs[i], hashmap))
: {
: result = vs[i];
: break;
: }
: }
: 为什么这里break了？不是要找最长的么？你这里只是找到一个由dict里面的单词构成
: 的单词之后就break了吧？
| g*********n
发帖数: 43 | 7 这两句放在循环里面好像有点奇怪:
for(int i = 1; i <= s.size(); i++)
{
. . .
{
if(s.size() == 0)
return true;
既然i从1开始, 那么(s.size() == 0) 就不会为true? | c********t
发帖数: 5706 | 8 haha, my baby 骑士.
下面这样难道不行？我不会c++, 大概写的。是我没读懂题吗？
string findLongestWord(vector &vs)
{
int maxlen=0;
string longest="";
for(int i=0; i< vs.size(); i++){
if(vs[i].length > maxlen){
maxlen=vs[i].length;
longest=vs[i];
}
}
return longest;
}
【在 B********t 的大作中提到】
: 求问一遍怎么扫
| e****e
发帖数: 418 | 9 "题目：找dict中最长的单词，这个单词必须由dict里的单词组成。"
是这个单词必须由dict里的<<其他>>单词组成？
例如：dict: foot, ball, football, basketball
result: football
请问小骑士是这样的末？
【在 c********t 的大作中提到】
: haha, my baby 骑士.
: 下面这样难道不行？我不会c++, 大概写的。是我没读懂题吗？
: string findLongestWord(vector &vs)
: {
: int maxlen=0;
: string longest="";
: for(int i=0; i< vs.size(); i++){
: if(vs[i].length > maxlen){
: maxlen=vs[i].length;
: longest=vs[i];
| c********t
发帖数: 5706 | 10 好像弄明白你的题意了。虽然我不懂c++,不过我觉得你的问题是，findLongestWord_
helper又想split to several words才能true, 又想如果剩一个词也要true
看看改成下面的行不
bool findLongestWord_helper(string &s, map &hm，bool hasSplit)
{
for(int i = 1; i <= s.size(); i++)
{
string sub_f(s, 0, i);
if(hm[sub_f])
{
if(i==s.size() ) return hasSplit;
string sub_b(s, i, s.size()-i);
if(findLongestWord_helper(sub_b, hm, true))
return true;
}
}
return false;
}
再继续说说，我的一点建议
1. c++没有hashset吗？如果有，应该把map换成set
2. 凡是findLongestWord_helper返回结果为true的都应该存在一个hashset里，这个
hashset 就是由dict里的单词组成的单词的cache，避免重复计算。
★ 发自iPhone App: ChineseWeb 7.8
★ 发自iPhone App: ChineseWeb 7.8
【在 B********t 的大作中提到】
: 题目：找dict中最长的单词，这个单词必须由dict里的单词组成。
: bool myfunc(string s1, string s2)
: {
: return (s1.size() > s2.size());
: }
: bool findLongestWord_helper(string &s, map &hm)
: {
: for(int i = 1; i <= s.size(); i++)
: {
: string sub_f(s, 0, i);
| | | j******2
发帖数: 362 | | B********t
发帖数: 147 | 12 啊。。。。我知道我错在哪了。。。 我应该只检查其它的单词 原代码所有单词
都检查了所以不管怎么样都会返回true....... thanks啦！
【在 e****e 的大作中提到】
: "题目：找dict中最长的单词，这个单词必须由dict里的单词组成。"
: 是这个单词必须由dict里的<<其他>>单词组成？
: 例如：dict: foot, ball, football, basketball
: result: football
: 请问小骑士是这样的末？
| B********t
发帖数: 147 | 13 噢 是的 我已经改过来了 是当i == s.size() 时就可以退出了 typo 我最初的
问题不是出在这里 是出在我连这个单词本身也检查了 所以永远都会返回true
【在 g*********n 的大作中提到】
: 这两句放在循环里面好像有点奇怪:
: for(int i = 1; i <= s.size(); i++)
: {
: . . .
: {
: if(s.size() == 0)
: return true;
: 既然i从1开始, 那么(s.size() == 0) 就不会为true?
| B********t
发帖数: 147 | 14 小冷骑士 多谢建议 我也刚学c++不久
c++里有set和map set是avl树实现的 map是红黑树实现的 为什么这里要用set而不
是map呢？
如果用set就是这样
bool myfunc(string s1, string s2)
{
return (s1.size() > s2.size());
}
bool findLongestWord_helper(string &s, set &hs)
{
for(int i = 1; i <= s.size(); i++)
{
string sub_f(s, 0, i);
if(hs.find(sub_f) != hs.end())
{
if(i == s.size())
return true;
string sub_b(s, i, s.size()-i);
if(findLongestWord_helper(sub_b, hs))
return true;
}
}
return false;
}
string findLongestWord(vector &vs)
{
string result("");
sort(vs.begin(), vs.end(), myfunc);
set hashset;
for(int i = 0; i < vs.size(); i++)
hashset.insert(vs[i]);
for(int i = 0; i < vs.size(); i++)
{
hashset.erase(vs[i]);
if(findLongestWord_helper(vs[i], hashset))
{
result = vs[i];
break;
}
hashset.insert(vs[i]);
}
return result;
}
hasSplit)
【在 c********t 的大作中提到】
: 好像弄明白你的题意了。虽然我不懂c++,不过我觉得你的问题是，findLongestWord_
: helper又想split to several words才能true, 又想如果剩一个词也要true
: 看看改成下面的行不
: bool findLongestWord_helper(string &s, map &hm，bool hasSplit)
: {
: for(int i = 1; i <= s.size(); i++)
: {
: string sub_f(s, 0, i);
: if(hm[sub_f])
: {
| B********t
发帖数: 147 | 15 恩 好像150里也有这道 是google的面试题吧
【在 j******2 的大作中提到】
: 是150里那道吗？
| c********t
发帖数: 5706 | 16 节省空间啊，map里面的value沒有用。另外我在我写的codes里改了一个bug. 现在应该
行了。
★ 发自iPhone App: ChineseWeb 7.8
【在 B********t 的大作中提到】
: 小冷骑士 多谢建议 我也刚学c++不久
: c++里有set和map set是avl树实现的 map是红黑树实现的 为什么这里要用set而不
: 是map呢？
: 如果用set就是这样
: bool myfunc(string s1, string s2)
: {
: return (s1.size() > s2.size());
: }
: bool findLongestWord_helper(string &s, set &hs)
: {
|
|
