算法才是灵魂
2019-05-15 08:50 百度_核心搜索部rank_算法工程师
关注
楼主，基于字典树的第21行会出现越界问题，比如case： zyyhappy zyy 不同长度的解决方案，用标识isEnd来控制，贴一下我的代码，如果有问题，还望各位指正。 #include <iostream>
#include <list>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
class Tire
{
public:
Tire *next[26];
bool isEnd;
Tire()
{
for(int i = 0 ; i < 26 ;i++)
next[i] = nullptr;
isEnd = false;
}
};
bool findSS(Tire *root, string s)
{
for(int i=0 ; i < s.size() ;i++)
{
int index = s[i] - 'a';
if(root->next[index] == nullptr)
return false;
root = root->next[index];
}
return root->isEnd;
}
void addTire(Tire* node, string word)
{
for(int i = 0 ; i < word.size() ;i++)
{
int index = word[i] - 'a';
if(node->next[index] == nullptr)
node->next[index] = new Tire();
node = node->next[index];
}
node->isEnd = true;
}
int main()
{
int t,n;
string s;
cin >> t;
while(t--)
{
cin >> n;
Tire *root = new Tire();
vector<string> v;
bool sign = false;
for(int i = 0 ; i < n ; i++)
{
cin >> s;
string new_s = s+s;
for(int k = 0 ; k < s.size()+1 ;k++)
{
string find_s = new_s.substr(k,s.size());
if(findSS(root,find_s))
{
sign = true;
break;
}
reverse(find_***egin(), find_s.end());
if(findSS(root, find_s))
{
sign = true;
break;
}
}
addTire(root, s);
}
if(sign) cout << "Yeah" << endl;
else cout << "Sad" << endl;
}
}
查看原帖
点赞 评论
查看8道真题和解析
牛客热帖
更多
正在热议
更多
# 实习生的蛐蛐区 #
1009481次浏览 5139人参与
# 求职遇到的搞笑事件 #
196936次浏览 980人参与
# 发面经攒人品 #
8911414次浏览 98813人参与
# 体制内上岸心路历程 #
38962次浏览 221人参与
# 27届实习投递记录 #
167164次浏览 1685人参与
# 担心入职之后被发现很菜怎么办 #
307434次浏览 1218人参与
# 你收到了团子的OC了吗 #
1639633次浏览 11864人参与
# 万物皆可发面经 #
5769次浏览 73人参与
# 扒一扒那些奇葩实习经历 #
160894次浏览 1184人参与
# 招聘要求与实际实习内容不符怎么办 #
226992次浏览 1078人参与
# 实习，不懂就问 #
232191次浏览 1771人参与
# AI了，我在打一种很新的工 #
212180次浏览 2371人参与
# HR问：你期望的薪资是多少？如何回答 #
103360次浏览 841人参与
# 父母对你找工作是助力还是阻力？ #
53820次浏览 474人参与
# 秋招盘点:机械人值得去的企业 #
109000次浏览 746人参与
# 实习最想跑路的瞬间 #
147843次浏览 787人参与
# 你知道哪些职场黑话？ #
94387次浏览 489人参与
# 你的mentor是什么样的人？ #
67484次浏览 855人参与
# 查收我的offer竞争力报告 #
303548次浏览 1758人参与
# 实习如何「偷」产出？ #
777579次浏览 8771人参与