建设网站用什么技术,网站优化qq群,赤峰市做网站建设的公司,免费网站建设特色问题描述
在广告平台中#xff0c;为了给广告主一定的自由性和效率#xff0c;允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候#xff0c;会根据用户的搜索词触发的 bidword 对创意中的通配符#xff08;通配符是用成对 {} 括起来的字符串#x…问题描述
在广告平台中为了给广告主一定的自由性和效率允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候会根据用户的搜索词触发的 bidword 对创意中的通配符通配符是用成对 {} 括起来的字符串可以包含 0 个或者多个字符进行替换用来提升广告投放体验。例如“{末日血战} 上线送 SSR 英雄三天集齐无敌阵容”会被替换成“帝国时代游戏下载上线送 SSR 英雄三天集齐无敌阵容”。给定一个含有通配符的创意和n个标题判断这句标题是否从该创意替换生成的。
测试样例
样例1
输入n 4, template “ad{xyz}cdc{y}f{x}e”, titles [“adcdcefdfeffe”, “adcdcefdfeff”, “dcdcefdfeffe”, “adcdcfe”] 输出“True,False,False,True”
样例2
输入n 3, template “a{bdc}efg”, titles [“abcdefg”, “abefg”, “efg”] 输出“True,True,False”
样例3
输入n 5, template “{abc}xyz{def}”, titles [“xyzdef”, “abcdef”, “abxyzdef”, “xyz”, “abxyz”] 输出“True,False,True,True,True”
思路分析
看到这个题的第一想法就是 题目并没有说明数据范围如果数据范围过大不上点手段的话肯定无法a掉的 但是这道题只是简单难度所以猜它的数据规模并不大暴力大概率能过。但是写暴力感觉很无聊脑袋中突然想到我们在实际开发过程中也会遇到这种匹配的问题比如邮箱格式验证等。 所以我们这里可以使用正则表达式来解决由于正则学的不咋样这里求救了一下伟大的GPT之神顺利a掉。 时间复杂度: O ( n ⋅ ( k ⋅ m p q ) ) O(n\cdot(k\cdot mpq)) O(n⋅(k⋅mpq)) 其中 n n n标题数量 k k k模板中的 {} 数量 m m m模板长度 p p p正则表达式长度 q q q标题长度。
#include iostream
#include string
#include vector
#include regex
using namespace std;bool isGeneratedTitle(const string templateStr, const string title) {// 将模板中的通配符 {} 替换为正则表达式 (.*)string pattern templateStr;size_t pos 0;// 替换所有的 {} 为 (.*)while ((pos pattern.find({, pos)) ! string::npos) {size_t end pattern.find(}, pos);if (end string::npos) break; pattern.replace(pos, end - pos 1, (.*?));pos 4; }// 在正则表达式中添加开始和结束标记pattern ^ pattern $;// 使用正则表达式匹配regex re(pattern);return regex_match(title, re);
}std::string solution(int n, std::string template_,std::vectorstd::string titles) {// Please write your code herestring ans ;for(int i 0; i n; i){if(ans.size() ! 0){ans ,;}if (isGeneratedTitle(template_, titles[i])){ans True;} else {ans False;}}return ans;
}
